GDCPC Kera's line segment (二维树状数组)

Mean

Sol

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int lmx=3000;
const int N = 3e3+10;
multiset<int>ve[3001];
multiset<int>::iterator it;
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lowbit(x) (x&(-x))
#define rep(i,a,b) for(int i=a;i<=b;++i)
struct node{
	int tr[N][N];
	int tr1[N][N];
	void init(){
		for(int i=1;i<N;++i){
            for(int j=1;j<N;++j){
                tr1[i][j]=0x3f3f3f3f;
                tr[i][j]=0;
            }
        }
	}
	void update(int l,int r,int val){
        l=3001-l;
		while(l<N){
            int rr=r;
            while(rr<N){
                tr1[l][rr]=min(tr1[l][rr],val);         
			    tr[l][rr]=max(tr[l][rr],val);
               rr+=lowbit(rr);
           }
           l+=lowbit(l);
		}
	}
	
	int get1(int l,int r){
		int mx=0,mi=0x3f3f3f3f;
        l=3001-l;
		while(l){
            int rr=r;
            while(rr){
                mi=min(tr1[l][rr],mi);         
			    mx=max(tr[l][rr],mx);
               rr-=lowbit(rr);
           }
           l-=lowbit(l);
		}
		return max(0,(mx-mi));
	}
	
}tt;
int main(){
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	int ans=0;
	tt.init();
	rep(i,1,n){
		int l,r,val;
		scanf("%d%d%d",&l,&r,&val);
		tt.update(l,r,val);
	}
	rep(i,1,m){
		int op,l,r,val;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&l,&r,&val);
			l=(l^ans),r=(r^ans);
			if(l>r)swap(l,r);
			tt.update(l,r,val);
		}
		else{
			scanf("%d%d",&l,&r);
			l=(l^ans),r=(r^ans);
			if(l>r)swap(l,r);
			ans=tt.get1(l,r);
			printf("%d\n",ans);
         
		}
	}
	return 0;
}
上一篇:Java并发46:并发集合系列-基于锁分段技术的ConcurrentHashMap


下一篇:opencv line