2018年湖南省第十四届大学生计算机程序设计竞赛 CSU 2170: 千万别用树套树

红太狼 2022-05-13 01:26 147阅读 0赞

[题目传送门][Link 1]  
比赛时想的解法，整体二分+树状数组  
具体看代码吧

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=100000+100;
    
    struct Node{
    	
    	int l,r;
    	int type,id;
    };
    int n,q;
    Node node[maxn],a[maxn],b[maxn];
    int tree[maxn],user[maxn],tot;
    int ans[maxn];
    
    void Add(int x){
    	
    	while(x<=n){
    		
    		if(user[x]!=tot) user[x]=tot,tree[x]=0;
    		tree[x]++;
    		x+=(x&(-x));
    	}
    }
    
    int getsum(int x){
    	
    	int sum=0;
    	while(x){
    		
    		if(user[x]!=tot) user[x]=tot,tree[x]=0;
    		sum+=tree[x];
    		x-=(x&(-x));
    	} 
    	return sum;
    }
    
    void kaven(int l,int r,int L,int R){
    
        tot++;
    	if(L==R){
    		
    		for(int i=l;i<=r;i++){
    			
    			if(node[i].type==1) Add(node[i].r);
    			else ans[node[i].id]+=(getsum(n)-getsum(node[i].r-1));
    		}
    		return ;
    	}
    	int mid=(L+R)>>1;
    	int atot=0,btot=0;
    	for(int i=l;i<=r;i++){
    		
    		if(node[i].type==1){
    			
    			if(node[i].l<=mid) Add(node[i].r),a[atot++]=node[i];
    			else b[btot++]=node[i];
    		}
    		else{
    			
    			if(node[i].l>mid) ans[node[i].id]+=(getsum(n)-getsum(node[i].r-1)),b[btot++]=node[i];
    			else if(node[i].l==mid) ans[node[i].id]+=(getsum(n)-getsum(node[i].r-1));
    			else a[atot++]=node[i];
    		}
    	}
    	for(int i=0;i<atot;i++) node[l+i]=a[i];
    	for(int i=0;i<btot;i++) node[l+atot+i]=b[i];
    	if(atot) kaven(l,l+atot-1,L,mid);
    	if(btot) kaven(l+atot,l+atot+btot-1,mid+1,R);
    }
    
    int main(){
    	
    	while(scanf("%d%d",&n,&q)==2){
    		
    		int Id=0;
    		tot=0;
    		memset(tree,0,sizeof(tree));
    		memset(user,0,sizeof(user));
    		memset(ans,0,sizeof(ans));
    		for(int i=1;i<=q;i++){
    			
    			scanf("%d%d%d",&node[i].type,&node[i].l,&node[i].r);
    			if(node[i].type==2) node[i].id=++Id;
    			else node[i].id=0;
    		}
    		kaven(1,q,1,n);
    		for(int i=1;i<=Id;i++) printf("%d\n",ans[i]);
    	}
    }

[Link 1]: http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2170