HDU 1540 Tunnel Warfare（用set解决线段树中单点查询）_综合

题目链接：
HDU 1540 Tunnel Warfare
题意:
有 $n$ 个村庄，编号为 $1--n$ ，相邻的村庄是直接连通的，村庄之间可以间接连通。
有 $m$ 个操作，分三种：
① $D x$ 表示破坏村庄 $x$ ，也就是说 $x$ 无法其连通作用。
② $Q x$ 表示查询村庄 $x$ 能连接到的最大村庄个数。
③ $R$ 表示修复上一次被破坏的村庄。
对每次查询输出结果。
分析：
参考博文链接
将被破坏的点放进 $set$ 中，每次查询只需要查找是否在集合中，如果在 $set$ 中那么说明就被破坏了，否则找到集合中第一个 $>=x$ 的键值，就代表 $x$ 能连接的右极限，键值-1就代表左极限。修复就从 $set$ 中删除上一次被破坏的 $x$ 。
$CODE:$

//1676K 436MS
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;const int maxn=50005;set<int> S;
int n,m,x,top;
int q[maxn];
char s[100];int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifwhile(~scanf("%d%d",&n,&m)){top=0;S.clear();S.insert(0);S.insert(n+1);for(int i=0;i<m;i++){scanf("%s",s);if(s[0]=='R'){if(top==0) continue;x=q[top--];S.erase(x);}else{scanf("%d",&x);if(s[0]=='D'){q[++top]=x;S.insert(x);//将被破坏的点放进set}else{if(S.find(x)!=S.end()) printf("0\n");//在集合中找到了被破坏的点else{set<int>:: iterator it=S.lower_bound(x);//找到集合中在点x右侧的第一个被破坏的点//set<int>:: iterator it=lower_bound(S.begin(),S.end(),x);int right=(*(it))-1;//right是能连接到的最右侧的点--it;//这时迭代器it指向点x左侧的第一个被破坏的点int left=(*(it))+1;//left是点x能连接到的最左端的点printf("%d\n",right-left+1);}}}}}return 0;
}

纯线段树写法：

//4160K 514MS
#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
using namespace std;const int maxn=50005;int n,m,x;
int des[maxn],top;
char s[10];struct SegTree{int left,right;int rr,ll,mm;//rr、ll、mm分别表示节点从左端点、从右端点以及节点整个区间的最大连续连通个数
}segtree[maxn<<2];void build(int left,int right,int cur)
{segtree[cur].left=left;segtree[cur].right=right;segtree[cur].ll=segtree[cur].rr=segtree[cur].mm=right-left+1;if(left==right) return ;int mid=(left+right)>>1;build(left,mid,lson(cur));build(mid+1,right,rson(cur));
}void update(int d,int flag,int cur)//更新是更新到叶子节点
{int left=segtree[cur].left;int right=segtree[cur].right;if(left==right)//其实left==right==d{if(flag==1) segtree[cur].ll=segtree[cur].rr=segtree[cur].mm=1;//修复else segtree[cur].ll=segtree[cur].rr=segtree[cur].mm=0;//破坏return ;}int mid=(left+right)>>1;if(d<=mid)//更新的节点在左子树{update(d,flag,lson(cur));}else update(d,flag,rson(cur));if(segtree[lson(cur)].ll==segtree[lson(cur)].right-segtree[lson(cur)].left+1) //左儿子全部连通segtree[cur].ll=segtree[lson(cur)].ll+segtree[rson(cur)].ll;else segtree[cur].ll=segtree[lson(cur)].ll;if(segtree[rson(cur)].rr==segtree[rson(cur)].right-segtree[rson(cur)].left+1) //左儿子全部连通segtree[cur].rr=segtree[rson(cur)].rr+segtree[lson(cur)].rr;else segtree[cur].rr=segtree[rson(cur)].rr;segtree[cur].mm=max(max(segtree[lson(cur)].mm,segtree[rson(cur)].mm),segtree[lson(cur)].rr+segtree[rson(cur)].ll);//整个区间的最大连通数是左儿子区间的最大连通数、右儿子区间的最大连通数、//左儿子的右端点的最大连通+右儿子的左端点的最大连通三者中的最大值
}int query(int d,int cur)
{int left=segtree[cur].left;int right=segtree[cur].right;if(left==right||segtree[cur].mm==0||segtree[cur].mm==right-left+1) return segtree[cur].mm;//到达叶子结点or区间内无连续连通点or区间内所有点都连通int mid=(left+right)>>1;if(d<=mid)//在左子树{if(d>=segtree[lson(cur)].right-segtree[lson(cur)].rr+1)//在左子树的右端连续区间内return segtree[lson(cur)].rr+segtree[rson(cur)].ll;else query(d,lson(cur));}else{if(d<=segtree[rson(cur)].left+segtree[rson(cur)].ll-1)//在右子树的左端连续区间内return segtree[lson(cur)].rr+segtree[rson(cur)].ll;else query(d,rson(cur));}
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifwhile(~scanf("%d%d",&n,&m)){top=-1;build(1,n,1);for(int i=0;i<m;i++){scanf("%s",s);if(s[0]=='D'){scanf("%d",&x);des[++top]=x;update(x,0,1);}else if(s[0]=='R'){if(top==-1) continue;x=des[top--];update(x,1,1);}else{scanf("%d",&x);printf("%d\n",query(x,1));}}}return 0;
}