95pts求助,WA on #2
查看原帖
95pts求助,WA on #2
275079
Rainylower楼主2023/11/7 18:12

第二个点的第221行std输出的是1,但following输出的是2,求助为何.

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

int const maxn = 5e5 + 10;
int a[maxn];
int rt[maxn];

struct PSGT{
	#define mid (l+r)/2
	struct node{
		int ls,rs,val;
	}T[maxn*40];
	int dcnt = 0;
	int update(int lst,int l,int r,int v,int w){
		int rt = ++dcnt;
		T[rt] = T[lst];
		T[rt].val += w;
		if(l==r)return rt;
		if(v <= mid){
			T[rt].ls = update(T[lst].ls,l,mid,v,w);
		}else {
			T[rt].rs = update(T[lst].rs,mid+1,r,v,w);
		}
	//	T[rt].val = T[T[rt].ls].val + T[T[rt].rs].val;
		return rt;
	}
	int query(int lst,int now,int l,int r,int c){
		if(l==r)return T[now].val - T[lst].val;
		if(c <= mid){
			return query(T[lst].ls,T[now].ls,l,mid,c);
		}else {
			return query(T[lst].rs,T[now].rs,mid+1,r,c);
		}
	}
	#undef mid
}SGTT;

bool b[maxn];
signed main(){
//	freopen("2.in","r",stdin);
//	freopen("22.out","w",stdout);
	int n,m;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m ;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		b[a[i]] = 1;
		rt[i] = SGTT.update(rt[i-1],1,n,a[i],1);
	}
	while(m--){
	    int op;
	    cin >> op;
	    if(op==1){
	        int l,r,c;
	        cin >> l>>r>>c;
	        if(!b[c]){
	        	cout << 0<<'\n';
	        	continue;
	        }
			cout << SGTT.query(rt[l-1],rt[r],1,n,c) <<'\n'; 
	    }else {
	    	int x;
	    	cin >> x;
	    	if(x==n)continue;
	    	int tmp1 = a[x],tmp2 = a[x+1];
	    	swap(a[x],a[x+1]);
	    	rt[x] = SGTT.update(rt[x],1,n,tmp1,-1);
	    	rt[x] = SGTT.update(rt[x],1,n,tmp2,1);
	    }
	}
	return 0;
}
2023/11/7 18:12
加载中...