问题描述
抗日战争时期，华北平原广大地区进行了广泛的隧道战争。一般来说，通过隧道连接的村庄成一直线。除了两端的两个村外，每个村庄都与两个相邻的村直接相连。
入侵者经常对一些村庄发动袭击，并摧毁其中的部分隧道。八路军指挥官要求提供隧道和村庄的最新连接状态。如果某些村庄被严重隔离，则必须立即恢复连接！
输入项
输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。接下来的m行中的每行都描述一个事件。
下面以不同的格式描述了三种不同的事件：
D x：第x个村庄被摧毁。
Q：陆军司令部要求第x个村庄包括其自身直接或间接联系的村庄数。
R：最后被摧毁的村庄被重建。
输出量
在单独的一行中按顺序输出对陆军指挥官要求的答案。
sample input
7 9
D 3
sampl output
题意：一连串的村庄线性排布，D x 摧毁x村庄 R回复最后摧毁的村庄，Q x 询问x村庄左右最大连续的村庄数
线段树维护连续区间。
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
typedef struct Tree
{
int l,r;
int ssum;//此区间内最大连续和
//int sum_;//该节点以下的节点值得总和
int suml;//此区间得左端开始的最大连续和
int sumr;//此区间得右端开始的最大连续和
}Tree;
Tree t[maxn*4];
void pushup(int n){
//t[n].sum_=t[root*2].sum_+t[root*2+1].sum_;
if(t[2*n].suml==t[2*n].r-t[2*n].l+1)
t[n].suml=t[2*n].suml+t[2*n+1].suml;
else
t[n].suml=t[2*n].suml;
if(t[2*n+1].sumr==t[2*n+1].r-t[2*n+1].l+1)
t[n].sumr=t[2*n+1].sumr+t[2*n].sumr;
else
t[n].sumr=t[2*n+1].sumr;
t[n].ssum=max(max(t[n*2].ssum,t[n*2+1].ssum),(t[n*2].sumr+t[n*2+1].suml));
}
void build(int n,int l,int r)
{
t[n].l=l;
t[n].r=r;
if(l==r)
{
//num=root;
t[n].ssum=t[n].suml=t[n].sumr=r-l+1;
// tree[root].ssum=power[left];
// tree[root].suml=power[left];
// tree[root].sum_=power[left];
// tree[root].sumr=power[left];
}
else
{
int mid=(l+r)/2;
build(n*2,l,mid);
build(n*2+1,mid+1,r);
pushup(n);
}
}
int query_sum(int n,int k)
{
if(t[n].l==t[n].r)
return t[n].ssum;
else{
int mid=(t[n].l+t[n].r)/2;
if( k <= mid )
if(k>=t[2*n].r-t[2*n].sumr+1)
return t[2*n].sumr+t[2*n+1].suml;
else
return query_sum(2*n,k);
else {
if( k<=t[2*n+1].l+t[2*n+1].suml-1)
return t[2*n].sumr+t[2*n+1].suml;
else
return query_sum(2*n+1,k);
}
}
}
void update(int n,int pos,int value)
//更新函数就是先不断二分找到位置，然后要像建树一样合并区间
{
if(t[n].l==t[n].r){
t[n].ssum=value;
t[n].suml=value;
// t[n].sum_=value;
t[n].sumr=value;
}
else
{
int mid=(t[n].l+t[n].r)/2;
if(pos<=mid)
update(2*n,pos,value);
else
update(2*n+1,pos,value);
pushup(n);
}
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
char s[5];
int a[maxn];
int x;
int cnt=0;
build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%s",s);
if(s[0]==‘D‘){
scanf("%d",&x);
a[cnt++]=x;
update(1,x,0);
}
if(s[0]==‘Q‘){
scanf("%d",&x);
printf("%d\n",query_sum(1,x));
}
if(s[0]==‘R‘){
update(1,a[--cnt],1);
}
}
}
return 0;
}
原文：https://www.cnblogs.com/lyj1/p/11922261.html