题意翻译 小唐纳德决定一天洗完他的白色床单。洗完后，他把它们放在后院的地上晾干。唐纳德把床单放在上面，使它们之间角或边不会互相接触，边也不会相交，但他可能把较小的床单放在大的上面，或者一个完全覆盖另个。做完这件事后，唐纳德上床睡觉了。
唐纳德的朋友基姆不知怎么地得到了唐纳德正在烘干他的床单的消息，决定和他捣乱。他在阁楼上找到了他父亲的彩弹枪。除了枪之外，还有不同颜色的彩弹球，但有可能有很多的球是相同的颜色。唐纳德一睡着，基姆走进他的后院，开始用他的彩弹枪射击床单。我们都知道床单会渗水，所以当基姆射出最上面的那张床单时，那张床单会把球的颜色渗到下面的所有床单上。基姆用了所有的球后，他愉快地离开了唐纳德的后院。
当唐纳德醒过来去拿床单时，非常震惊。在唐纳德的大部分床单上都有一些新的颜色。由于唐纳德对正确的数据很感兴趣，他太震惊了，以至于无法思考，他要求你告诉他每张床单上的新颜色的数量。
我们可以把唐纳德的后院表示成一个无限坐标系，而这些床单是平行于坐标轴的矩形。基姆的彩弹可以表示为该系统中的点。
请注意：基姆的彩弹可能没有打到任何一张床单，但是每一个彩弹的坐标都是独一无二的。
输入的第一行包含正整数床单的数量n（1≤n≤80000）和彩弹球数m（1≤m≤80000）。
接下来的n行中的每一行包含四个数字：表示左下角的坐标Ai,Bi(1≤Ai,Bi≤1000000000)和右上角的坐标Ci,Di(1 ≤Ci,Di≤1000000000)。
接下来的M行中的每一行包含三个数字，包含基姆投篮的坐标Xj,Yj(1≤Xj,Yj≤1000000000)，第j个球的颜色Kj(1≤Kj≤1000000000)。
共n行，每一行必须包含在第i张床单上的新颜色的数量。
题目描述 Little Donald decided to wash all N of his white sheets one day. After washing them, he put them to dry on the ground in his backyard. Donald placed the sheets so that ** none of them touch on the tips or the sides and that none of their sides intersect**, but it is possible that he placed smaller sheets on top of bigger ones, or that a sheet is completely covering another sheet. After doing this, Donald went to bed.
Donald’s friend Kim somehow got the information that Donald is drying his sheets and decided to mess with him. He found a paintball gun from his father in the attic. Along with the gun, there were M paintball balls in different colours, but it is possible that there were more balls having the same colour. As soon as Donald fell asleep, Kim walked into his backyard and started shooting the sheets with his paintball gun. We all know that sheets bleed, so when Kim shoots the topmost sheet, that sheet would bleed the color of the ball down to all of the sheets beneath it. After Kim used all the balls, he happily left Donald’s backyard.
When Donald woke up and went to get his sheets, shock ensued. On most of Donald’s sheets, there was a number of new colours. Since Donald is very interested in correct data, and he’s in shock and not able to think, he is asking you to tell him the number of new colours on each sheet.
We can represent Donald’s backyard as an infinite coordinate system, and the sheets as rectangles parallel to the coordinate axes. Kim’s shots can be represented as points in that system.
Please note: it is possible that Kim’s shot missed all the sheets, but coordinates of each shot are unique.
输入格式 The first line of input contains the positive integers N (1 ≤ N ≤ 80 000), the number of sheets, and M (1 ≤ M ≤ 80 000), the number of paintball balls.
The i^{th}ith of the following N lines contains four numbers: the coordinates of the lower left corner A_iAi, B_iBi (1 ≤ A_iAi, B_iBi ≤ 10^9109) and the upper right corner C_iCi, D_iDi, (1 ≤ C_iCi, D_iDi ≤ 10^9109) of the i^{th}ith sheet.
The j^{th}jth of the following M lines contains the coordinates where Kim’s j^{th}jth shot landed X_jXj, Y_jYj (1 ≤X_jXj, Y_jYj ≤ 10^9109), and K_jKj(1 ≤ K_jKj ≤ 10^9109), the colour label of the j^{th}jth ball.
输出格式 The i^{th}ith of N lines must contain the number of new colours on the i^{th}ith sheet.
输入输出样例 输入 #1复制 2 2 1 1 3 3 5 6 10 10 3 3 1 5 1 2 输出 #1复制 1 0 输入 #2复制 3 3 1 1 7 7 2 2 6 6 3 3 5 5 4 4 1 2 6 2 4 7 3 输出 #2复制 3 2 1 输入 #3复制 1 3 1 1 7 7 2 6 2 4 7 3 4 4 1 输出 #3复制 3 说明/提示
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<queue> #include<ctime> #define MAXN 200005 #define ll long long #define maxn 15 #define maxs 1000005 #define inf 1e9 #define eps 1e-9 using namespace std; inline char gc() { static char now[1<<16],*S,*T; if (T==S) { T=(S=now)+fread(now,1,1<<16,stdin); if (T==S) return EOF; } return *S++; } inline ll readlong() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x*=10; x+=ch-'0'; ch=getchar(); } return x*f; } inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x*=10; x+=ch-'0'; ch=getchar(); } return x*f; } void putint(long long t) { int ans[40]= {0}; for(; t; t/=10)ans[++ans[0]]=t; for(; ans[0]; ans[0]--)putchar('0'+ans[ans[0]]); putchar('\n'); } const int N=500005; int n,m; struct edge{ int to,nxt; }e[N]; int h[N],cnt; void add(int x,int y){ e[++cnt]=(edge){y,h[x]}; h[x]=cnt; } int pre[N],_k[N],_y[N],rt[N]; int ans[N]; int dx,dy,dv; int g[N<<5]; int col[N<<5],f[N<<5][2]; int cntt,cnty,cnts; int tot; struct bed{ int x,y,k,i; bool operator <(const bed &a)const{ if(x==a.x){ return i>a.i; } return x<a.x; } }mp[N<<2]; int query(int x,int l,int r){ if(g[x]>=0||l==r){ return g[x]; } if(!x){ return 0; } int mid=(l+r)>>1; if(dx<=mid){ return query(x<<1,l,mid); } else{ return query(x<<1|1,mid+1,r); } } void push(int x){ if(g[x]<0){ return ; } g[x<<1]=g[x<<1|1]=g[x]; g[x]=-1; } void modify(int x,int l,int r){ if(dx<=l&&dy>=r){ g[x]=dv; return ; } push(x); int mid=(l+r)>>1; if(dx<=mid){ modify(x<<1,l,mid); } if(dy>mid){ modify(x<<1|1,mid+1,r); } } void add_cor(int &x,int l,int r){ if(!x){ x=++tot; } if(l==r){ col[x]=1; return; } int mid=(l+r)>>1; if(dx<=mid){ add_cor(f[x][0],l,mid); } else{ add_cor(f[x][1],mid+1,r); } col[x]=col[f[x][0]]+col[f[x][1]]; } int merge(int a,int b,int l,int r){ if(!a|!b){ return a^b; } if(l==r){ return a; } int mid=(l+r)>>1; f[a][0]=merge(f[a][0],f[b][0],l,mid); f[a][1]=merge(f[a][1],f[b][1],mid+1,r); col[a]=col[f[a][0]]+col[f[a][1]]; return a; } void dfs(int x){ for(int i=h[x];i;i=e[i].nxt){ int y=e[i].to; if(y!=pre[x]){ dfs(y); rt[x]=merge(rt[x],rt[y],1,cnts); } } ans[x]=col[rt[x]]; } int main(){ memset(g,-1,sizeof(g)); n=read(); m=read(); for(int i=1;i<=n;i++){ int a=read(); int b=read(); int c=read(); int d=read(); mp[++cntt]=(bed){a,b,d,i}; _y[++cnty]=b; mp[++cntt]=(bed){c,b,d,-i}; _y[++cnty]=d; } for(int i=1;i<=m;i++){ int x=read(); int y=read(); int k=read(); mp[++cntt]=(bed){x,y,k,0}; _y[++cnty]=y; _k[++cnts]=k; } sort(_y+1,_y+1+cnty); cnty=unique(_y+1,_y+1+cnty)-_y-1; sort(_k+1,_k+1+cnts); cnts=unique(_k+1,_k+1+cnts)-_k-1; sort(mp+1,mp+cntt+1); for(int i=1;i<=cntt;i++){ mp[i].y=lower_bound(_y+1,_y+1+cnty,mp[i].y)-_y; if(mp[i].i){ mp[i].k=lower_bound(_y+1,_y+1+cnty,mp[i].k)-_y; if(mp[i].i>0){ dx=mp[i].y; dy=mp[i].k; dv=mp[i].i; if((pre[dv]=query(1,1,cnty))>0){ add(pre[dv],dv); } modify(1,1,cnty); continue; } dx=mp[i].y; dy=mp[i].k; dv=max(pre[-mp[i].i],0); modify(1,1,cnty); continue; } mp[i].k=lower_bound(_k+1,_k+cnts+1,mp[i].k)-_k; dx=mp[i].y; int tmp=query(1,1,cnty); if(tmp>0){ dx=mp[i].k; add_cor(rt[tmp],1,cnts); } } for(int i=1;i<=n;i++){ if(pre[i]<=0){ dfs(i); } } for(int i=1;i<=n;i++){ printf("%d\n",ans[i]); } return 0;}