10/3： 牛客 2020 tg1

挂大分，现在做题面临一个困境，就是有思路而不会实现。

A

一眼裴蜀定理，注意除以0的情况啊啊啊啊啊啊。

B

换个不同于题解的思路解释。

每一次询问事实上就是把第 \(l-1\) 个操作后的排列变成初始局面，做到第 \(r\) 个操作。注意到这样的置换与值是无关的，改变的只是相对位置，于是维护操作的“前缀和”，每一次询问把第 \(l-1\) 次操作后的排列按照 \(0\sim 9\) 编号，然后输出 \(r\) 里面对应的编号即可。（也就是说每次操作改变的只是编号，这个编号可以是任意的初始值，操作结束后按照编号一一对应就行了）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N=1e5+10;

int n,m;
int pos[N][10];

void calc(int l,int r){
    int temp[10];
    for(int i=0;i<10;++i)temp[pos[l][i]]=i;
    for(int i=0;i<10;++i)cout<<temp[pos[r][i]]<<" " ;
    cout<<"\n";
}

int main() {
    cin>>n>>m;
    for(int i=0;i<10;++i)pos[0][i]=i;
    for(int i=1;i<=n;++i){
        int l,r;cin>>l>>r;
        for(int j=0;j<10;++j)pos[i][j]=pos[i-1][j];
        swap(pos[i][l],pos[i][r]);
    }
    while(m--){
        int l,r;cin>>l>>r;
        calc(l-1,r);
    }
    return 0;
}

C

原题

假设答案为 \(res\)，显然 \([0,res)\) 是能被表示出来的。

则我们维护能凑出来的区间，设为 \([0,res]\)，从小到大加数，若加入的 \(a_i>res+1\)，则 \(res+1\) 一定不能表示出来，就是答案了。

若 \(a_i\le res+1\)，则 \([0,res+a_i]\) 一定能表示出，\(res\leftarrow res+a_i\)，继续加数。

做一次这样的时间复杂度是 \(O(\log V\log n)\) 的，证明：

设上一次确定的 \(res\) 是 \(pre\)，则新加的数一定 \(\ge pre+1\) 且 \(\le res+1\)，要么没有，故每次操作后总和至少会翻倍或者不变。每次找新加的数可以用主席树做，故得证。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

typedef long long ll;
#define int ll

int n,m;
int rt[N],cnt=0,ls[N<<5],rs[N<<5],sum[N<<5];

void ins(int pre,int &cur,int l,int r,int pos,int v){
	if(!cur)cur=++cnt;
	sum[cur]=sum[pre]+v;
	if(l==r)return;
	int mid=l+r>>1;
	if(pos<=mid)rs[cur]=rs[pre],ins(ls[pre],ls[cur],l,mid,pos,v);
	else ls[cur]=ls[pre],ins(rs[pre],rs[cur],mid+1,r,pos,v);
}
int query(int pre,int cur,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return sum[cur]-sum[pre];
	int mid=l+r>>1,res=0;
	if(ql<=mid)res+=query(ls[pre],ls[cur],l,mid,ql,qr);
	if(qr>mid)res+=query(rs[pre],rs[cur],mid+1,r,ql,qr);
	return res;
}

signed main(){
	cin>>n>>m;
	for(int i=1,x;i<=n;++i)cin>>x,ins(rt[i-1],rt[i],1,1e9,x,x);
	while(m--){
		int l,r,res=0,pre=0,qwq=0;
		cin>>l>>r;
		while(1){
			qwq=query(rt[l-1],rt[r],1,1e9,pre+1,res+1);
			if(qwq)pre=res+1,res+=qwq;
			else break;
		}
		cout<<res+1<<"\n";
	}
	return 0;
}

D

CDQ？李超树？还没学先缓一缓。