秋实大哥与战争
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
男儿何不带吴钩，收取关山五十州。
征战天下是秋实大哥一生的梦想，所以今天他又在练习一个对战游戏。
秋实大哥命令所有士兵从左到右排成了一行来抵挡敌人的攻击。
敌方每一次会攻击一个士兵，这个士兵就会阵亡，整个阵列就会从这个位置断开；同时有的时候已阵亡的士兵会受人赢气息感染而复活。
秋实大哥想知道某一时刻某一个士兵所在的阵列的长度是多少。
Input
第一行包含两个整数nn，mm，表示秋实大哥的士兵数目和接下来发生的事件数目。
接下来mm行，每一行是以下三种事件之一：
0 x : 表示x位置的士兵受到攻击阵亡
1 x : 表示x位置的士兵受人赢气息感染复活
2 x : 秋实大哥想知道第x个士兵所在阵列的长度
1≤n，m≤1000001≤n，m≤100000，1≤x≤n。1≤x≤n。
Output
对于每一个22 xx事件，输出对应的答案占一行。
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 3 2 2 0 3 2 2 |
5 2 |
Source
2015 UESTC Training for Data Structures
板子题；
#include<bits/stdc++.h> using namespace std; #define ll __int64 #define mod 1000000007 #define pi (4*atan(1.0)) const int N=1e5+10,M=4e6+10,inf=1e9+10; struct is { int l,r; int lm,mm,rm; }tree[N<<2]; void buildtree(int l,int r,int pos) { tree[pos].l=l; tree[pos].r=r; tree[pos].lm=tree[pos].rm=tree[pos].mm=(r-l+1); if(l==r) return; int mid=(l+r)>>1; buildtree(l,mid,pos<<1); buildtree(mid+1,r,pos<<1|1); } void update(int point,int change,int pos) { if(tree[pos].l==point&&tree[pos].r==point) { tree[pos].lm=tree[pos].mm=tree[pos].rm=change; return; } int mid=(tree[pos].l+tree[pos].r)>>1; if(point<=mid) update(point,change,pos<<1); else update(point,change,pos<<1|1); tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm)); tree[pos].rm=tree[pos<<1|1].rm; tree[pos].lm=tree[pos<<1].lm; if(tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1) tree[pos].rm+=tree[pos<<1].rm; if(tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1) tree[pos].lm+=tree[pos<<1|1].lm; } int query(int x,int pos) { if(tree[pos].l==tree[pos].r||tree[pos].mm==0||tree[pos].mm==tree[pos].r-tree[pos].l+1) return tree[pos].mm; int mid=(tree[pos].r+tree[pos].l)>>1; if(x<=mid) { if(x>=tree[pos<<1].r-tree[pos<<1].rm+1) return query(x,pos<<1)+query(mid+1,pos<<1|1); else return query(x,pos<<1); } else { if(x<=tree[pos<<1|1].lm+tree[pos<<1|1].l-1) return query(x,pos<<1|1)+query(mid,pos<<1); else return query(x,pos<<1|1); } } int main() { int x,y,z,i,t; while(~scanf("%d%d",&x,&y)) { buildtree(1,x,1); while(y--) { int flag,x; scanf("%d%d",&flag,&x); if(flag==0||flag==1) update(x,flag,1); else printf("%d ",query(x,1)); } } return 0; }