考虑到颜色只有50种
所以我们开50棵线段树 然后对于每次询问 循环50次对于每一个颜色的线段树询问
那如何查询啊
你考虑到每次询问的最左边都是1
也就是说只需要对于每种颜色的纵坐标 维护往右出现过的点的横坐标的最小值
然后就是区间(y1,y2)查询最小值 判断是否超过了x
但是会MLE啊
所以动态开点 复杂度为nlogn
#include<bits/stdc++.h> #define N 55 #define DIS 1000000 #define maxn 1000010 using namespace std; struct Node { int l,r; int lson,rson; int sum,minc; }tree[4*maxn]; int tot,root[N]; bool flag; void update(int &now,int l,int r,int x,int y) { if(!now) now=++tot; tree[now].l=l; tree[now].r=r; tree[now].minc=min(tree[now].minc,x); tree[now].sum++; if(l==r) return; int m=(l+r)>>1; if(y<=m) update(tree[now].lson,l,m,x,y); else update(tree[now].rson,m+1,r,x,y); } void query(int now,int l,int r,int up) { if(!now||flag) return; if(l<=tree[now].l&&tree[now].r<=r) { if(tree[now].minc<=up&&tree[now].sum>0) flag=1; return; } int m=(tree[now].l+tree[now].r)>>1; if(l<=m) query(tree[now].lson,l,r,up); if(r>m) query(tree[now].rson,l,r,up); } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int opt; for(int i=0;i<maxn*4;i++) tree[i].minc=DIS+5; while(cin>>opt) { if(opt==3) return 0; //exit if(opt==0) //clear { memset(root,0,sizeof(root)); for(int i=0;i<=tot;i++) { tree[i].lson=tree[i].rson=tree[i].l=tree[i].r=tree[i].sum=0; tree[i].minc=DIS+5; } tot=0; } else if(opt==1) { int x,y,c; cin>>x>>y>>c; update(root[c],1,DIS,x,y); } else if(opt==2) { int x,y1,y2; cin>>x>>y1>>y2; int ans=0; for(int i=0;i<=50;i++) { flag=false; query(root[i],y1,y2,x); if(flag) ans++; } cout<<ans<<'\n'; } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9833666.html
