[BZOJ 1176:单点修改，查询子矩阵和]:
1176: [Balkan2007]Mokia
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 2005 Solved: 894
[Submit][Status][Discuss]
Description
维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
Input
第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小
接下来每行为一下三种输入之一(不包含引号):
"1 x y a"
"2 x1 y1 x2 y2"
"3"
输入1:你需要把(x,y)(第x行第y列)的格子权值增加a
输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出
输入3:表示输入结束
Output
对于每个输入2,输出一行,即输入2的答案
Sample Input
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
5
HINT
保证答案不会超过int范围
Source
分析：
第一道CDQ分治的题目TAT...
我理解的CDQ分治就是通过离线去掉时间的限制(或者某一维的限制)，把动态修改问题转化为静态查询问题...
对于这道题来说，我们可以把查询操作分为4个询问前缀和的操作...
我们把所有的操作按照x排序，那么我们查询的时候维护y的树状数组就可以...这样达到了降维的目的...
我们把操作按照x排序，然后对于当前操作区间[l,r]，可以应用分治的思想，把区间按照时间为关键字分为[l,mid]和[mid+1,r]两个区间(在两个区间内x依然有序)，对于区间内部的修改操作对查询操作的影响，这是一个相同的子问题，所以我们递归解决即可...我们只需要处理的就是[l,mid]中的修改操作对[mid+1,r]中的查询操作的影响...这个树状数组处理即可...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//大鹏一日同风起，扶摇直上九万里 const int maxn=+,maxm=+; struct M{
int x,y,val,pos,ans;
M() {}
M(int a,int b,int c,int d);
}q[maxm],q2[maxm]; int n,m,op,T,tr[maxn],tim[maxn]; M :: M(int a=,int b=,int c=,int d=){
x=a,y=b,val=c,pos=d,ans=;
} inline void insert(int x,int y){
for(;x<=n;x+=x&(-x)){
if(tim[x]!=T)
tr[x]=;
tim[x]=T,tr[x]+=y;
}
} inline int query(int x){
int res=;
for(;x;x-=x&(-x))
if(tim[x]==T)
res+=tr[x];
return res;
} inline bool cmp1(M a,M b){
return a.x<b.x;
} inline bool cmp2(M a,M b){
return a.pos<b.pos;
} inline void CDQ(int l,int r){
if(l==r)
return;
int mid=(l+r)>>,l1=l,l2=mid+;
for(int i=l;i<=r;i++){
if(q[i].pos<=mid)
q2[l1++]=q[i];
else
q2[l2++]=q[i];
}
memcpy(q+l,q2+l,sizeof(q[])*(r-l+));CDQ(l,mid);
int j=l;T++;
for(int i=mid+;i<=r;i++){
for(;q[j].x<=q[i].x&&j<=mid;j++)
if(q[j].val!=)
insert(q[j].y,q[j].val);
if(q[i].val==)
q[i].ans+=query(q[i].y);
}
CDQ(mid+,r);
l1=l,l2=mid+;
for(int i=l;i<=r;i++){
if((q[l1].x<q[l2].x&&l1<=mid)||l2>r)
q2[i]=q[l1++];
else
q2[i]=q[l2++];
}
memcpy(q+l,q2+l,sizeof(q[])*(r-l+));
} signed main(void){
int l,s,x,y;m=;
scanf("%d%d",&n,&n);
while(scanf("%d",&op)&&op!=){
if(op==)
scanf("%d%d%d",&x,&y,&s),q[++m]=M(x,y,s,m);
else
scanf("%d%d%d%d",&l,&s,&x,&y),
q[++m]=M(l-,s-,,m),
q[++m]=M(l-,y ,,m),
q[++m]=M(x ,s-,,m),
q[++m]=M(x ,y ,,m);
}
sort(q+,q+m+,cmp1);CDQ(,m);sort(q+,q+m+,cmp2);
for(int i=,lala;i<=m;i++)
if(q[i].val==){
lala =q[i++].ans;
lala-=q[i++].ans;
lala-=q[i++].ans;
lala+=q[i ].ans;
printf("%d\n",lala);
}
return ;
}//Cap ou pas cap. Cap.
[BZOJ 3163：背包问题]：
3163: [Heoi2013]Eden的新背包问题
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 382 Solved: 252
[Submit][Status][Discuss]
Description
“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”
失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？
Input
第一行一个数n，表示有n个玩偶，玩偶从0开始编号
第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需
要的价钱，获得的价值以及第i个玩偶的限购次数。
接下来的一行为q，表示询问次数。
接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）
Output
输出q行，第i行输出对于第 i个询问的答案。
Sample Input
2 3 4
1 2 1
4 1 2
2 1 1
3 2 3
5
1 10
2 7
3 4
4 8
0 5
Sample Output
11
6
12
4
HINT
一共五种玩偶，分别的价钱价值和限购次数为 (2,3,4)， (1,2,1)， (4,1,2)， (2,1,1)，(3,2,3)。五个询问，以第一个询问为例。第一个询问表示的是去掉编号为1的玩偶，且拥有的钱数为10时可以获得的最大价值，则此时剩余玩偶为(2,3,4)，(4,1,2)，(2,1,1)，(3,2,3)，若把编号为0的玩偶买4个（即全买了），然后编号为3的玩偶买一个，则刚好把10元全部花完，且总价值为13。可以证明没有更优的方案了。注意买某种玩偶不一定要买光。
100. 数据满足1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105 , 1 ≤ a
i、bi、c i ≤ 100, 0 ≤ d i < n, 0 ≤ei ≤ 1000。
Source
分析：
对于删除物品分治...
我们定义CDQ(l,r)为删除[l,r]这个区间的物品的dp值，那么递归到[l,l]的时候就可以更新答案了...
怎么计算...因为[l,mid]的dp值一定包含了[mid+1,r]之间的物品，所以我们可以用[mid+1,r]之间的物品更新dp值之后传入[l,mid]进行计算，同理，用[l,mid]的物品更新dp值然后传入[mid+1,r]进行计算...
其实为了保证复杂度要用单调队列优化背包...但是这题数据水...我很懒...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//大鹏一日同风起，扶摇直上九万里 const int maxn=+,maxq=+; int n,m,cnt,v[maxq],co[maxn],hd[maxn],ans[maxq],pos[maxq],nxt[maxq],val[maxn],num[maxn],f[][maxn]; inline void add(int s,int x,int y){
pos[cnt]=y;v[cnt]=s;nxt[cnt]=hd[x];hd[x]=cnt++;
} inline void dp(int *f,int x){
for(int i=;i<=num[x];i++)
for(int j=maxn-;j>=co[x];j--)
f[j]=max(f[j],f[j-co[x]]+val[x]);
} inline void CDQ(int l,int r,int d){
if(l==r){
for(int i=hd[l];i!=-;i=nxt[i])
ans[pos[i]]=f[d-][v[i]];
return;
}
int mid=(l+r)>>;
for(int i=;i<maxn;i++)
f[d][i]=f[d-][i];
for(int i=mid+;i<=r;i++)
dp(f[d],i);
CDQ(l,mid,d+);
for(int i=;i<maxn;i++)
f[d][i]=f[d-][i];
for(int i=l;i<=mid;i++)
dp(f[d],i);
CDQ(mid+,r,d+);
} signed main(void){
scanf("%d",&n);cnt=;
memset(hd,-,sizeof(hd));
for(int i=;i<=n;i++)
scanf("%d%d%d",&co[i],&val[i],&num[i]);
scanf("%d",&m);
for(int i=,x,y;i<=m;i++)
scanf("%d%d",&x,&y),add(y,x+,i);
CDQ(,n,);
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}//Cap ou pas cap. Cap.
[BZOJ 3237: 无向图是否联通]:
3237: [Ahoi2013]连通图
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1155 Solved: 396
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Sample Output
Disconnected
Connected
HINT
N<=100000 M<=200000 K<=100000
Source
分析：
一开始想的是CDQ(l,r)代表的是删掉[l,r]这一整段区间的边无向图的状态，但是发现酱紫是不行滴...
然后我们发现我们可以对query进行分治，CDQ(l,r)代表的是去掉[l,r]这段询问的边无向图的状态...我们用并查集来维护...
学习到一个新的方法...用栈来维护并查集的压缩过程，这样可以回溯...
因为并查集没有按秩合并...所以被YSQ吐槽为“叽里咕噜滚雪球式并查集”...(￣_￣|||)...
好吧...按秩合并确实快...4s和12s的差距TAT...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//大鹏一日同风起，扶摇直上九万里 const int maxn=+,maxm=+; int n,m,Q,T,tail,fa[maxn],ans[maxn],stk[maxn*],vis[maxm]; struct M{
int num,id[];
}q[maxn]; struct G{
int x,y;
}e[maxm]; inline int find(int x){
if(fa[x]==x)
return x;
stk[++tail]=x;stk[++tail]=fa[x];
return fa[x]=find(fa[x]);
} inline void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)
stk[++tail]=fx,stk[++tail]=fx,fa[fx]=fy;
} inline void CDQ(int l,int r){
int mid=(l+r)>>,lala=tail;
if(l==r){
for(int i=;i<=q[l].num&&ans[l];i++)
if(find(e[q[l].id[i]].x)!=find(e[q[l].id[i]].y))
ans[l]=;
while(lala!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
return;
}T++;
for(int i=l;i<=mid;i++)
for(int j=;j<=q[i].num;j++)
vis[q[i].id[j]]=T;
for(int i=mid+;i<=r;i++)
for(int j=;j<=q[i].num;j++)
if(vis[q[i].id[j]]!=T)
merge(e[q[i].id[j]].x,e[q[i].id[j]].y);
CDQ(l,mid);T++;
while(lala!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
for(int i=mid+;i<=r;i++)
for(int j=;j<=q[i].num;j++)
vis[q[i].id[j]]=T;
for(int i=l;i<=mid;i++)
for(int j=;j<=q[i].num;j++)
if(vis[q[i].id[j]]!=T)
merge(e[q[i].id[j]].x,e[q[i].id[j]].y);
CDQ(mid+,r);
while(lala!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
} signed main(void){
scanf("%d%d",&n,&m);
memset(vis,-,sizeof(vis));
for(int i=;i<=m;i++)
scanf("%d%d",&e[i].x,&e[i].y);
scanf("%d",&Q);
for(int i=;i<=Q;i++){
scanf("%d",&q[i].num);ans[i]=;
for(int j=;j<=q[i].num;j++)
scanf("%d",&q[i].id[j]),vis[q[i].id[j]]=;
}
for(int i=;i<=n;i++)
fa[i]=i;
for(int i=;i<=m;i++)
if(vis[i]==-)
merge(e[i].x,e[i].y);
CDQ(,Q);
for(int i=;i<=Q;i++)
ans[i]?puts("Connected"):puts("Disconnected");
return ;
}//Cap ou pas cap. Cap.
[BZOJ 2001:动态最小生成树]:
2001: [Hnoi2010]City 城市建设
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 1129 Solved: 552
[Submit][Status][Discuss]
Description
PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis决定求助于你来完成这个任务。
Input
文件第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。 接下来M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。
Output
输出包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。
Sample Input
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3
Sample Output
10
9
HINT
【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据，n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。
Source
分析：
这道题的思想主要在于通过分治来缩小图的规模，从而降低复杂度...
我们定义CDQ(l,r)为处理[l,r]的询问...那么这个时候[1,l-1]的边已经固定了...
有一下两个操作：
No.1 合并必须边：
我们把[l,r]的边设为-inf，跑最小生成树，树边就是必须边...(原因自己YY)...
No.2 删除多余边：
我们把[l,r]的边设为+inf，跑最小生成树，非树边是多余边...
然后递归边界为[l,l]这个时候跑最小生成树然后加上合并的权值就是当前的ans...
讲道理...这题主要是细节...我调了好久...要了数据才过...(好吧其实数据没有什么用...看样例就100了...这没法调啊w(ﾟДﾟ)w)
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define inf 0x3f3f3f3f
using namespace std; const int maxn=+,maxm=+; int n,m,Q,T,tail,fa[maxn],stk[maxn*],ver[],edg[],vis[maxm]; long long ans[maxm],val[],w[maxm]; struct M{
int x,y,w,flag,id;
friend bool operator < (M a,M b){
return a.w<b.w;
}
}G[][maxm],lala[maxm],lalala[maxm]; struct L{
int id,w;
}q[maxm]; inline int find(int x){
if(fa[x]==x)
return x;
stk[++tail]=x,stk[++tail]=fa[x];
return fa[x]=find(fa[x]);
} inline void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)
stk[++tail]=fx,stk[++tail]=fx,fa[fx]=fy;
} inline long long kruskal(int d){
sort(lala+,lala+edg[d]+);long long res=;
for(int i=;i<=edg[d];i++){
int fx=find(lala[i].x),fy=find(lala[i].y);
if(fx!=fy)
merge(fx,fy),res+=w[lala[i].id],lala[i].flag=;
else
lala[i].flag=;
}
return res;
} inline void CDQ(int l,int r,int d){
int tmp=tail,ttmp;
if(l==r){
w[q[l].id]=q[l].w;
for(int i=;i<=edg[d-];i++)
lala[i]=G[d-][i],lala[i].w=w[G[d-][i].id];
ans[l]=kruskal(d-)+val[d-];
while(tmp!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
return;
}
edg[d]=edg[d-],val[d]=val[d-],ver[d]=ver[d-];
int mid=(l+r)>>;T++;
for(int i=l;i<=r;i++)
vis[q[i].id]=T;
for(int i=;i<=edg[d];i++){
lala[i]=G[d-][i],lala[i].w=w[G[d-][i].id];
if(vis[G[d-][i].id]==T)
lala[i].w=-inf;
}
kruskal(d);
while(tmp!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
int haha=edg[d];
for(int i=,j=;i<=haha;i++){
if(lala[i].flag&&lala[i].w!=-inf)
merge(lala[i].x,lala[i].y),ver[d]--,edg[d]--,val[d]+=w[lala[i].id];
else
lala[i].x=find(lala[i].x),lala[i].y=find(lala[i].y),G[d][++j]=lala[i],G[d][j].w=w[lala[i].id];
}ttmp=tail;
for(int i=;i<=edg[d];i++){
G[d][i].x=find(G[d][i].x),G[d][i].y=find(G[d][i].y);
lala[i]=G[d][i],lala[i].w=w[G[d][i].id];
if(vis[G[d][i].id]==T)
lala[i].w=inf;
}
kruskal(d);
while(ttmp!=tail)
fa[stk[tail-]]=stk[tail],tail-=;
haha=edg[d];
for(int i=,j=;i<=haha;i++){
if(!lala[i].flag&&lala[i].w!=inf)
edg[d]--;
else
lala[i].x=fa[lala[i].x],lala[i].y=fa[lala[i].y],G[d][++j]=lala[i];
}
CDQ(l,mid,d+),CDQ(mid+,r,d+);
while(tail!=tmp)
fa[stk[tail-]]=stk[tail],tail-=;
} signed main(void){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++)
scanf("%d%d%d",&G[][i].x,&G[][i].y,&G[][i].w),G[][i].id=i,w[i]=G[][i].w;
for(int i=;i<=Q;i++)
scanf("%d%d",&q[i].id,&q[i].w);
for(int i=;i<=n;i++)
fa[i]=i;
edg[]=m,ver[]=n,CDQ(,Q,);
for(int i=;i<=Q;i++)
printf("%lld\n",ans[i]);
return ;
}//Cap ou pas cap. Cap.
[BZOJ2716 平面最近点]:
2716: [Violet 3]天使玩偶
Time Limit: 80 Sec Memory Limit: 128 MB
Submit: 1476 Solved: 623
[Submit][Status][Discuss]
Description
Input
Output
分析：
和第一道题目是一样的，只不过是把求和变成了取max...
首先我们可以以当前询问的点为原点，把平面划分为4个部分，我们首先考虑左下角的点dis[i,j]=x[i]-x[j]+y[i]-y[j]=x[i]+y[i]-(x[j]+y[j])...
这样我们只需要查询当前点左下角的点x+y最大的点即可，那么还是按照x排序维护y的树状数组...
那么其他三个区域的点可以对称一下转化为左下角的点...
但是这题它卡常数...我人帅自带大常数TAT...T死了...
所以就把O(nlgn)的四个排序改成了四个memcpy...然后就A了QAQ...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define inf 0x7fffffff
using namespace std;
//大鹏一日同风起，扶摇直上九万里 const int maxn=+,maxm=+; int n,m,T,Max,tr[maxm],tim[maxm],ans[maxm]; struct M{
int t,x,y,id;
bool operator <(const M &a)const{
if(x!=a.x)
return x<a.x;
return t<a.t;
}
}q[maxn],q2[maxn],l[maxn]; inline int read(void){
char ch=getchar();int f=,x=;
while(!(ch>=''&&ch<='')){
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
x=x*+ch-'',ch=getchar();
return f*x;
} inline void insert(int x,int y){
for(;x<=Max;x+=x&-x){
/*
if(tim[x]!=T)
tr[x]=-1;
tim[x]=T,tr[x]=max(tr[x],y);
*/
if(tim[x]!=T||tr[x]<y)
tr[x]=y,tim[x]=T;
}
} inline int query(int x){
int res=-;
for(;x;x-=x&-x)
if(tim[x]==T)
res=max(tr[x],res);
return res;
} /*
inline void CDQ(int l,int r){
if(l==r)
return;
int mid=(l+r)>>1,l1=l,l2=mid+1;
for(int i=l;i<=r;i++){
if(q[i].id<=mid)
q2[l1++]=q[i];
else
q2[l2++]=q[i];
}
for(int i=l;i<=r;i++)
q[i]=q2[i];
CDQ(l,mid);int j=l;T++;
for(int i=mid+1;i<=r;i++){
for(;q[j].x<=q[i].x&&j<=mid;j++)
if(q[j].t==1)
insert(q[j].y,q[j].x+q[j].y);
if(q[i].t==2){
int lala=query(q[i].y);
q[i].ans=lala==-1?q[i].ans:min(q[i].x+q[i].y-lala,q[i].ans);
}
}
CDQ(mid+1,r);
l1=l,l2=mid+1;
for(int i=l;i<=r;i++){
if((q[l1].x<q[l2].x&&l1<=mid)||l2>r)
q2[i]=q[l1++];
else
q2[i]=q[l2++];
}
for(int i=l;i<=r;i++)
q[i]=q2[i];
}
*/ inline void CDQ(int l,int r){
if(l==r)
return;
int mid=(l+r)>>,l1=l,l2=mid+;
CDQ(l,mid),CDQ(mid+,r);
for(int i=l;i<=r;i++){
if((l1<=mid&&q[l1]<q[l2])||l2>r)
q2[i]=q[l1++];
else
q2[i]=q[l2++];
}
for(int i=l;i<=r;i++)
q[i]=q2[i];
T++;
for(int i=l;i<=r;i++){
if(q[i].t==&&q[i].id>mid){
int lala=query(q[i].y);
ans[q[i].id]=lala==-?ans[q[i].id]:min(q[i].x+q[i].y-lala,ans[q[i].id]);
}
else if(q[i].t==&&q[i].id<=mid)
insert(q[i].y,q[i].x+q[i].y);
}
} signed main(void){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n=read(),m=read();Max=;T=;m+=n;
for(int i=;i<=n;i++){
l[i].x=read()+,l[i].y=read()+,l[i].id=i,l[i].t=;
if(l[i].x>Max)
Max=l[i].x;
if(l[i].y>Max)
Max=l[i].y;
}
for(int i=n+;i<=m;i++){
l[i].t=read(),l[i].x=read()+,l[i].y=read()+,l[i].id=i,ans[i]=inf;
if(l[i].x>Max)
Max=l[i].x;
if(l[i].y>Max)
Max=l[i].y;
}
Max++; /*
sort(q+1,q+m+1);CDQ(1,m);
for(int i=1;i<=m;i++)
q[i].x=Max-q[i].x;
sort(q+1,q+m+1);CDQ(1,m);
for(int i=1;i<=m;i++)
q[i].y=Max-q[i].y;
sort(q+1,q+m+1);CDQ(1,m);
for(int i=1;i<=m;i++)
q[i].x=-(q[i].x-Max);
sort(q+1,q+m+1);CDQ(1,m);
*/ memcpy(q,l,sizeof(q));
CDQ(,m); memcpy(q,l,sizeof(q));
for(int i=;i<=m;i++)
q[i].x=Max-q[i].x;
CDQ(,m); memcpy(q,l,sizeof(q));
for(int i=;i<=m;i++)
q[i].y=Max-q[i].y;
CDQ(,m); memcpy(q,l,sizeof(q));
for(int i=;i<=m;i++)
q[i].x=Max-q[i].x,q[i].y=Max-q[i].y;
CDQ(,m); for(int i=n+;i<=m;i++)
if(l[i].t==)
printf("%d\n",ans[i]);
return ;
}//Cap ou pas cap. Cap.
By NeighThorn