Tunnel Warfare

Time Limit: 1 Sec  Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=1540

Description

Input

Output

Sample Input

Sample Output

HINT

题意

给你一个区间，有三个操作，使的一个村庄毁灭，使的上一个毁灭的村庄复活，查询这个村庄所在最长区间

题解：

啊，就是一个区间合并的简单线段树，单点修改，记录从左边的最大值，右边的最大值，区间的最大值

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 150001
#define mod 10007
#define eps 1e-9
//const int inf=0x7fffffff;   //无限大
const int inf=0x3f3f3f3f;
/*

int buf[10];
inline void write(int i) {
  int p = 0;if(i == 0) p++;
  else while(i) {buf[p++] = i % 10;i /= 10;}
  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);
  printf("\n");
}
*/
//**************************************************************************************
inline ll read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct node{
    int l,r;
    int len;
    int lm,rm,mm;
};
node a[maxn*4];

void build(int l,int r,int x){
    a[x].l=l,a[x].r=r;
    a[x].lm=a[x].rm=a[x].len=a[x].mm=r-l+1;
    if(l!=r){
        int mid=(l+r)>>1;
        build(l,mid,x<<1);
        build(mid+1,r,x<<1|1);
    }
}
void updata(int i,int t,int x)
{
    if(a[i].l == a[i].r){a[i].lm = a[i].rm = a[i].mm = x;return;}
    int mid = (a[i].l+a[i].r)>>1;
    if(t<=mid)updata(2*i,t,x);
    else updata(2*i+1,t,x);
    a[i].lm = a[2*i].lm;
    a[i].rm = a[2*i+1].rm;
    a[i].mm = max(max(a[2*i].mm,a[2*i+1].mm),a[2*i].rm+a[2*i+1].lm);
    if(a[2*i].lm == a[2*i].r-a[2*i].l+1)a[i].lm += a[2*i+1].lm;
    if(a[2*i+1].rm == a[2*i+1].r-a[2*i+1].l+1)a[i].rm += a[2*i].rm;
}
int query(int x,int p)
{
    if(a[x].l==a[x].r||a[x].mm==0||a[x].mm==a[x].len)
        return a[x].mm;
    int mid=(a[x].l+a[x].r)>>1;
    if(p<=mid){
        if(p>=a[x<<1].r-a[x<<1].rm+1)
            return query(x<<1,p)+query(x<<1|1,mid+1);
        else
            return query(x<<1,p);
    }
    else{
        if(p<=a[x<<1|1].l+a[x<<1|1].lm-1)
            return query(x<<1|1,p)+query(x<<1,mid);
        else
            return query(x<<1|1,p);
    }
}

int main()
{
    int n,m,y;
    char x[3];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        stack<int> k;
        memset(a,0,sizeof(a));
        build(1,n,1);
        for(int i=0;i<m;i++)
        {
            scanf("%s",x);
            if(x[0]=='D')
            {
                y=read();
                updata(1,y,0);
                k.push(y);
            }
            else if(x[0]=='Q')
            {
                y=read();
                printf("%d\n",query(1,y));
            }
            else
            {
                updata(1,k.top(),1);
                k.pop();
            }
        }
    }
}