hdu 1540
题意：1-n个地道，m个次操作，D代表摧毁第i个地道，Q代表查询包含第i个地道的最大连续地道数目，并输出。R代表修复最近摧毁的那个地道。
思路：
（线段树&区间合并&最大连续区间）
充分利用了线段树相邻结点之间的区间都是连续的性质，x[rt]表示这个区间从左边起的连续区间的长度，y[rt]表示这个区间从右边起的连续区间的长度。
1.单点修改、区间合并，巧妙的地方是这一个区间的左连续区间x[rt]等于左孩子的长度加上右孩子的左连续区间（前提是左孩子的左连续区间x[rt<<1]等于左孩子的区间长度，也就是左孩子没有遭到破坏，反之x[rt]=x[rt<<1]），右孩子也是同样的道理。最基础的部分就是如果隧道被毁，就把只含这个隧道的区间赋值0，修复了就赋值1.
2.最大连续区间，先保证要求的隧道在该区间的左或右端点的连续区间内，如果不在左右某个连续区间内就查找子树。左右连续区间含该隧道的这一层，该隧道的最大连续区间（如果该隧道在该区间左连续区间上，如果是在该区间的右连续区间上也是一样算的）长度等于该区间的左连续长度加上左边区间的右连续长度。这里注意特判一下区间是根区间的情况，因为根区间没有左右兄弟区间。
Code；
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int sum[50001<<2],x[50001<<2],y[50001<<2];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void build(int l,int r,int rt) {
x[rt]=y[rt]=r-l+1;//初始时rt区间从左边开始和从右边开始的连续区间都是r-l+1
if(l==r) return;
int mid=l+r>>1;
build(lson);
build(rson);
}//初始化，全部的隧道都是联通的
void add(int a,int c,int l,int r,int rt) {
if(l==r) {
x[rt]=y[rt]=c;
return;
}//c==0表示隧道破坏，c==1表示隧道修复。
int mid=l+r>>1;
if(a<=mid) add(a,c,lson);
else add(a,c,rson);
if(x[rt<<1]==mid-l+1)
x[rt]=mid-l+1+x[rt<<1|1];
else x[rt]=x[rt<<1];
if(y[rt<<1|1]==r-mid)
y[rt]=r-mid+y[rt<<1];
else y[rt]=y[rt<<1|1];
}
int query(int a,int l,int r,int rt) {
if(rt==1) {
if(x[rt]>=a) {
return x[rt];
}
if(r-y[rt]+1<=a) {
return y[rt];
}
}
if(l+x[rt]-1>=a) {
return x[rt]+y[rt-1];
}
if(r-y[rt]+1<=a) {
return y[rt]+x[rt+1];
}
if(l==r) return 0;
int mid=l+r>>1;
if(a<=mid) return query(a,lson);
else return query(a,rson);
}
int n,m,k;
char ch;
stack<int>s;
int main() {
while(~scanf("%d%d",&n,&m)) {
build(1,n,1);
while(!s.empty()) s.pop();
while(m--) {
scanf(" %c",&ch);
if(ch=='D') {
read(k);
s.push(k);
add(k,0,1,n,1);
}
else if(ch=='Q') {
read(k);
printf("%d\n",query(k,1,n,1));
}
else {
if(s.empty()) continue;
k=s.top(); s.pop();
add(k,1,1,n,1);
}
}
}
return 0;
} 
poj 2155
题意：给一个空的二维矩阵，初始元素为0，有两种操作，C x1 y1 x2 y2将左上角到右下角的所有数反转一下，即0变1，1变0，Q x1 y1 ，询问当前坐标的值。题目给了t组数据，要求两组数据之间空一行。
思路：又是二维线段树，涉及到了区间的简单修改，和求单个点的值，所以不需要lazy操作。线段树结点保存的是更新的次数，奇数次为1，偶数次为0，修改[x,y]（这里讨论的是行，列也是一样的）区间时，如果当前区间是[x,y]的子区间，更新这里就好了，如果该区间和[x,y]相交，就查询这个区间的子区间。查询某个点的值时，只要加上根到这个结点路径上的全部值，然后如果值是奇数，这个点就是1，反之是0，因为我们修改区间并没有深入更深的子区间。
Code：
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int sum[1005<<2][1005<<2],n,ans;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void subupdate(int a,int b,int l,int r,int rt,int t) {
if(a<=l&&b>=r) {
sum[t][rt]^=1;
return;
}
int mid=l+r>>1;
if(a<=mid) subupdate(a,b,lson,t);
if(b>mid) subupdate(a,b,rson,t);
}
void update(int x1,int x2,int y1,int y2,int l,int r,int rt) {
if(x1<=l&&x2>=r) {
subupdate(y1,y2,1,n,1,rt);
return;
}
int mid=l+r>>1;
if(x1<=mid) update(x1,x2,y1,y2,lson);
if(x2>mid) update(x1,x2,y1,y2,rson);
}
void subquery(int a,int l,int r,int rt,int t) {
ans+=sum[t][rt];
if(l==r) return;
int mid=l+r>>1;
if(a<=mid) subquery(a,lson,t);
else subquery(a,rson,t);
}
void query(int x,int y,int l,int r,int rt) {
subquery(y,1,n,1,rt);
if(l==r) return;
int mid=l+r>>1;
if(x<=mid) query(x,y,lson);
else query(x,y,rson);
}
char ch;
int t,m;
int main() {
read(t);
while(t--) {
int x1,x2,y1,y2;
read(n),read(m);
memset(sum,0,sizeof sum);
while(m--) {
scanf(" %c",&ch);
if(ch=='C') {
read(x1),read(y1),read(x2),read(y2);
update(x1,x2,y1,y2,1,n,1);
}
else {
read(x1),read(y1);
ans=0;
query(x1,y1,1,n,1);
if(ans&1) puts("1");
else puts("0");
}
}
if(t) puts("");
}
return 0;
}
京公网安备 11010502036488号