HDU – 1540 Tunnel Warfare （[线段树] 最长连续子序列问题的区间合并/最长连续子序列问题转为区间最值问题）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <utility>
#include <stack>
using namespace std;
const int maxn = 1e6+10;
stack<int> s;
struct Node {
	int l;
	int r;
	int medium;
	int prefix;
	int suffix;
} tree[maxn<<2];
void pushup(int p, int len) {
	int left_interval = (len - len/2);//左区间长度
	int right_interval = len / 2;//右区间长度
	if(tree[p<<1].prefix==left_interval)//左区间左连续等于左区间长度
		tree[p].prefix = tree[p<<1].prefix+tree[p<<1|1].prefix;//p区间左连续延伸
	else
		tree[p].prefix = tree[p<<1].prefix;
	if(tree[p<<1|1].suffix==right_interval)
		tree[p].suffix = tree[p<<1].suffix+tree[p<<1|1].suffix;
	else
		tree[p].suffix = tree[p<<1|1].suffix;
	tree[p].medium = max(tree[p<<1].medium, tree[p<<1|1].medium);
	tree[p].medium = max(tree[p<<1].suffix+tree[p<<1|1].prefix, tree[p].medium);
}
void build(int p, int l, int r) {
	tree[p].prefix = tree[p].suffix = tree[p].medium = r-l+1;
	tree[p].l=l,tree[p].r=r;
	if(l==r) {
		return ;
	}
	int mid = (l+r)>>1;
	build(p<<1, l, mid);
	build(p<<1|1, mid+1, r);
//	pushup(p, r-l+1);
}
void update(int p, int idx, int x) {
	if(tree[p].l==tree[p].r && tree[p].l==idx) {
		tree[p].medium = tree[p].prefix = tree[p].suffix = x;
		return ;
	}
	int mid = (tree[p].l+tree[p].r)>>1;
	if(idx<=mid) update(p<<1, idx, x);
	if(idx>mid) update(p<<1|1, idx, x);
	pushup(p, tree[p].r-tree[p].l+1);
}
int query(int p, int idx) {
	if(tree[p].l==tree[p].r || tree[p].medium==0 ||tree[p].medium == (tree[p].r-tree[p].l+1)) {
		return tree[p].medium;
	}
	int mid = (tree[p].l+tree[p].r)>>1;
	if(idx<=mid) {
		//如果idx在左区间的右连续内，则需要加上右区间的左连续 
		if(idx>=mid-tree[p<<1].suffix+1) return query(p<<1, idx) + query(p<<1|1, mid+1);//这时候 
		else return query(p<<1, idx);
	}
	if(mid<idx) {
		//同理咯 
		if(idx<=mid+1+tree[p<<1|1].prefix-1) return query(p<<1, mid) + query(p<<1|1, idx);
		else return query(p<<1|1, idx);
	}
}
int main() {
	int n, q, x;
	char opt[10];
	while(scanf("%d%d", &n, &q)!=EOF) {
		while(!s.empty()) s.pop();
		build(1, 1, n);
		for(int i=0; i<q; ++i) {
			scanf("%s", opt);
			if(opt[0]=='D') {
				scanf("%d", &x);
				update(1, x, 0);
				s.push(x);
			}
			if(opt[0]=='Q') {
				scanf("%d", &x);
				printf("%d\n", query(1, x));
			}
			if(opt[0]=='R') {
				if(!s.empty()) {
					update(1, s.top(), 1);
					s.pop();
				}
			}
		}
	}
	return 0;
}

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn=1e6+10;
int a[maxn];
struct SegmentTree {
	int l,r;
	int maxx;
	int minn;
} t[maxn * 4];
int n; 
void build(int p,int l,int r) { //build(1，1，n) 1为根节点
	t[p].l=l,t[p].r=r;
	if(l==r) {
		t[p].maxx=0;
		t[p].minn=n+1;
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].maxx=max(t[p*2].maxx,t[p*2+1].maxx);
	t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
}
void change_min(int p,int x,int v) { //change(1,x,v) 1为根节点
	if(t[p].l==t[p].r) {
		t[p].minn=v;
		return ;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)change_min(p*2,x,v);
	else change_min(p*2+1,x,v);
	t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
}
void change_max(int p,int x,int v) {
	if(t[p].l==t[p].r) {
		t[p].maxx=v;
		return ;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)change_max(p*2,x,v);
	else change_max(p*2+1,x,v);
	t[p].maxx=max(t[p*2].maxx,t[p*2+1].maxx);
}
int ask_max(int p,int l,int r) { //ask(1,l,r) 1为根节点
	if(l<=t[p].l && r>=t[p].r)return t[p].maxx;
	int mid=(t[p].l + t[p].r)/2;
	int val=-(1<<30);
	if(l<=mid)val=max(val,ask_max(p*2,l,r));
	if(r>mid) val=max(val,ask_max(p*2+1,l,r));
	return val;
}
int ask_min(int p,int l,int r) { //ask(1,l,r) 1为根节点
	if(l<=t[p].l && r>=t[p].r)return t[p].minn;
	int mid=(t[p].l + t[p].r)/2;
	int val=1<<30;
	if(l<=mid)val=min(val,ask_min(p*2,l,r));
	if(r>mid) val=min(val,ask_min(p*2+1,l,r));
	return val;
}
int history[maxn];//保存历史，用于R
int main() {
	int m,a,temp,count;
	char ch[10];
	while(scanf("%d %d",&n,&m) == 2) {
		count = 0;  //历史计算器
		memset(history,0,sizeof(history));
		build(1,1,n);
		while(m--) {
			scanf("%s",ch);
			if(ch[0] == 'D') {
				scanf("%d",&a);
				change_min(1,a,a);//更新线段数的值，把a对应的值更新成a
				change_max(1,a,a);
				history[++count] = a;  //存储到历史记录中
			} else if(ch[0] == 'Q') {
				int re,max1,min1;
				scanf("%d",&a);
				max1=ask_max(1,1,a);//根据线段树查询
				min1=ask_min(1,a,n);
				if(max1 == min1)         //考虑特殊情况
					printf("%d\n",0);
				else
					printf("%d\n",min1-max1-1);
			} else {
				temp = history[count--];
				change_min(1,temp,n+1); //如果恢复，就把对应的值改为0或n+1
				change_max(1,temp,0);
			}
		}
	}
	return 0;
}