Answer key :

answer = suffix - Prefix -1

If you get blasted , Then it's time 0

Join in at the beginning 0,n+1, Make sure there are prefixes and suffixes

Code :

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
char s[];
int n,m,la[N],ppp,pre[N],in[N],x,size[N],c[N][],root,tot,data[N];
void rot(int x)
{
int y=pre[x],k=(c[y][]==x);
size[y]=size[c[y][k]]+size[c[x][k]]+;
size[x]=size[c[x][!k]]+size[y]+;
c[y][!k]=c[x][k];
pre[c[y][!k]]=y;
pre[x]=pre[y];
if(pre[y])c[pre[y]][c[pre[y]][]==y]=x;
c[x][k]=y;pre[y]=x;
}
void splay(int x,int g)
{
for(int y=pre[x];y!=g;rot(x),y=pre[x])
if(pre[y]!=g)rot((x==c[y][])==(y==c[pre[y]][])?y:x);
if(g==)root=x;
}
void insert(int x)
{
int y=root;
while(c[y][x>data[y]]) y=c[y][x>data[y]];
data[++tot]=x;
c[tot][]=c[tot][]=;
pre[tot]=y;
if(y)c[y][x>data[y]]=tot;
splay(tot,);
}
void del(int x)
{
int y=root;
while(data[y]!=x) y=c[y][x>data[y]];
splay(y,);
y=c[root][];
bool b;
if(!y) b=,y=c[root][];else b=;
while(c[y][b]) y=c[y][b];
splay(y,root);
c[y][b]=c[root][b];pre[c[root][b]]=y;pre[y]=;root=y;
size[y]=size[c[y][!b]]+size[c[y][b]];
}
int findpre(int x)
{
int ans;
for(int y=root;y;)
if(data[y]<x)ans=data[y],y=c[y][];
else y=c[y][];
return ans;
}
int findnxt(int x)
{
int ans;
for(int y=root;y;)
if(data[y]<=x)y=c[y][];
else ans=data[y],y=c[y][];
return ans;
}
int read()
{
int x=;char c;
for (;c<''||c>'';c=getchar());
for (;c>=''&&c<='';c=getchar())x=x*+c-;
return x;
}
void write(int x)
{
if (x>=)write(x/);
putchar(x%+);
}
int main()
{
n=read();m=read();
insert();insert(n+);
while (m--)
{
scanf("%s",&s);
if (s[]=='D')
{
x=read();
insert(x);
in[x]=;
la[++ppp]=x;
}
if (s[]=='Q')
{
x=read();
if (in[x])
{
puts("");
continue;
}
int l=findpre(x),r=findnxt(x);
write(r-l-);puts("");
}
if (s[]=='R'&&ppp)in[la[ppp]]=,del(la[ppp--]);
}
}

poj2892 More articles about

  1. [POJ2892]Tunnel Warfare

    [POJ2892]Tunnel Warfare Test description During the War of Resistance Against Japan, tunnel warfare was carried ...

  2. ACM Training program step 2 [ Not the original ]

    (Step2-500 topic )POJ Training program +SGU after Step1-500 Question training , And then we can start Step2-500 topic , Include POJ The training plan is 298 Title and SGU First two chapters 200 topic . need 1-1 We will continue to improve and solve problems for a year and a half ...

  3. ACM Syllabus

    1 Recommended question bank •http://ace.delos.com/usaco/ In the United States OI Question bank , If you're a beginner , Try to brush it through first , I can learn almost all the basic algorithms and optimize them , All the solutions and procedures of the problem and the translation of the problem can be b ...

  4. ACM The training program

    1. Algorithm summary and recommended topics 1.1 C++ STL • STL Containers : set, map, vector, priority_queue, queue, stack, deque, bitset• STL ...

  5. ACM Syllabus ( turn )

    1 Recommended question bank •http://ace.delos.com/usaco/ In the United States OI Question bank , If you're a beginner , Try to brush it through first , I can learn almost all the basic algorithms and optimize them , All the solutions and procedures of the problem and the translation of the problem can be b ...

  6. POJ Training program

    POJ Training program Step1-500 topic UVaOJ+ Introduction to algorithm competition classic + Challenge programming +USACO Please see :http://acm.sdut.edu.cn/bbs/read.php?tid=5321 One .POJ Training ...

Random recommendation

  1. scrapy Reptiles docker Deploy

    spider_docker Take my last blog , Create... For crawler references container, Modules included :scrapy, mongo, celery, rabbitmq, Connect https://github.com/Liu ...

  2. add to sudo jurisdiction

    Enter super user mode . That is input "su -", The system will let you enter the super user password , Enter the password and enter super user mode .( Of course , You can also use it directly root use ) Add write permission to file . That is, input the command " ...

  3. use NuGet Package Explorer Manage your siege weapons

    reason : One project at a time , Always from your own “ The magazine ” Or you can manually reference some class libraries and script plug-ins in previous projects , It's hard to avoid some tedious and omissions . Think of the things that are often used NuGet, Run to NuGet Home page , Found to have  NuGet Package ...

  4. linux NFS Server installation and configuration Ideas

    One ,nfs Advantages and disadvantages of service NFS yes Network File System Abbreviation , Network file system , Different clients can be mounted in the same directory , Use as shared storage , This can ensure the data consistency of different nodes , In the cluster architecture ...

  5. eclipse the user operation is waiting for building workspace&quot; to complete

    "the user operation is waiting for building workspace" to complete", terms of settlement : 1. Choose... From the menu bar “P ...

  6. python3.5 install pyHook, solve 【TypeError: MouseSwitch() missing 8 required positional arguments: &#39;msg&#39;, &#39;x&#39;, &#39;y&#39;, &#39;data&#39;, &#39;time&#39;, &#39;hwnd&#39;, and &#39;window_name&#39;】 This mistake !

    Why install pyHook package : by Windows Global mouse and keyboard events in provide callbacks . Python Application registers event handlers for user input events , For example, left mouse button , Left mouse button , Keyboard keys, etc First, we need to get the mouse position or keyboard input of the system in real time ...

  7. poj 3696 The Luckiest Number

    The Luckiest Number The main idea of the topic : To give you one int Positive integer in range n, Ask for the smallest x, bring : Successive x individual 8 Can be n to be divisible by . notes : If there is no solution output 0.poj Multiple sets of data , The first i Group data is preceded by Case ...

  8. logback Insert the reference code of database in batch

    protected void insertProperties(Map<String, String> mergedMap, Connection connection, long eve ...

  9. One bash command , Clear the specified network interface list

    stay K8S Installation and configuration process of , Because of constant testing , Will continue to generate a variety of virtual network interfaces . that , Do not re install before , Clean up the garbage interface generated last time , Don't let them affect the next test , It is necessary . How to delete it quickly ? Following commands ...

  10. Python Medium yield A brief introduction to the generator

    Python yield Use analysis ( Collated from : Liao xuefeng , Software engineer , HP 2012 year 11 month 22 Japan  ) Beginners Python Developers in the world often find a lot of Python The function uses yield Turn off ...