[luogu1503][鬼子进村]

题目链接

思路

将哪些村庄已经被摧毁了放到treap里。查询的时候如果当前村庄已经被毁了，那么就可以直接输出0.不然就输出这个村庄的后继-前驱-1。原因显然

代码

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<bitset>

#define ls TR[cur].ch[0]

#define rs TR[cur].ch[1]

using namespace std;

typedef long long ll;

const int N = 50100,INF = 60000;

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

int n,m;

struct node {

   int ch[2],val,id;

}TR[N];

void rotate(int &cur,int f) {

   int son = TR[cur].ch[f];

   TR[cur].ch[f] = TR[son].ch[f ^ 1];

   TR[son].ch[f ^ 1] = cur;

   cur = son;

}

int tot;

void insert(int &cur,int val) {

   if(!cur) {

      cur = ++tot;

      TR[cur].val = val;

      TR[cur].id = rand();

      return;

   }

   int d = val > TR[cur].val;

   insert(TR[cur].ch[d],val);

   if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);

}

void del(int &cur,int val) {

   if(!cur) return;

   if(TR[cur].val == val) {

      if(!ls || !rs) {cur = ls + rs;return;}

      int d = TR[ls].id > TR[rs].id;

      rotate(cur,d);

      del(cur,val);

   }

   else del(TR[cur].ch[val > TR[cur].val],val);

}

int pred(int cur,int val) {

   if(!cur) return 0;

   if(val > TR[cur].val) return max(TR[cur].val,pred(rs,val));

   return pred(ls,val);

}

int nex(int cur,int val) {

   if(!cur) return n + 1;

   if(val < TR[cur].val) return min(TR[cur].val,nex(ls,val));

   return nex(rs,val);

}

int sta[N],top;

int bz[N];

int main() {

   n = read(),m = read();

   char c;

   int rt = 0;

   while(m--) {

      cin>>c;

      if(c == 'D') {

         int x = read();

         insert(rt,x);

         sta[++top] = x;

         bz[x] = 1;

      }

      if(c == 'R') del(rt,sta[top--]),bz[sta[top + 1]] = 0;

      if(c == 'Q') {

         int x = read();

         if(bz[x]) { puts("0");continue;}

         int r = nex(rt,x),l = pred(rt,x);

         printf("%d\n",r - l -1);

      }

   }

   return 0;

}

一言

谁看见过风？我和你，都不曾看见过。