显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=50010;
int ma[240],L[240],R[240],tou[240],wei[240];
int X,D;
int belong[maxn];
bool vis[maxn];
int N,M,sz,sum;
void makeblock()
{
sz=sqrt(N*1.0);
for(sum=1;sum*sz<N;sum++)
{
L[sum]=(sum-1)*sz+1;
R[sum]=(sum)*sz;
tou[sum]=R[sum]-L[sum]+1;
wei[sum]=tou[sum];
ma[sum]=tou[sum];
for(int i=L[sum];i<=R[sum];i++)belong[i]=sum;
}
L[sum]=(sum-1)*sz+1;
R[sum]=N;
tou[sum]=R[sum]-L[sum]+1;
wei[sum]=tou[sum];
ma[sum]=tou[sum];
for(int i=L[sum];i<=R[sum];i++)belong[i]=sum;
/*for(int i=1;i<=sum;i++)
printf("%d %d\n",L[i],R[i]);*/
}
void get(int block,int l,int r)
{
// if(X==76&&D==10)printf("+++ %d \n",block);
if(tou[block]==wei[block]&&tou[block]==0&&!ma[block])
{
for(int i=L[block];i<l;i++)
{
vis[i]=1;
}
for(int i=r+1;i<=R[block];i++)
{
vis[i]=1;
}
}
if(tou[block]==R[block]-L[block]+1)
{
for(int i=L[block];i<l;i++)
{
vis[i]=0;
}
for(int i=r+1;i<=R[block];i++)
{
vis[i]=0;
}
}
int la=L[block]-1;
bool flag=0;
ma[block]=0,tou[block]=0,wei[block]=0;
for(int i=L[block];i<=R[block];i++)
{
if(i==R[block])
{
if(!vis[i])
{
wei[block]=i-la; if(!flag)tou[block]=wei[block];
}
else
{
wei[block]=0; if(!flag)tou[block]=i-1-la,ma[block]=max(tou[block],ma[block]);
}
ma[block]=max(ma[block],wei[block]);
//if(X==5&&D==5)printf("---- %d %d\n",i,ma[block]);
}
if(vis[i]&&!flag)
{
flag=1;
tou[block]=i-1-la;
ma[block]=max(tou[block],ma[block]);
la=i;
}
else if(vis[i]&&flag)
{
ma[block]=max(i-1-la,ma[block]);
la=i;
}
}
}
void REB(int pos)
{
int l=pos,r=pos+D-1;
if(belong[l]==belong[r])
{
for(int i=l;i<=r;i++)
{
vis[i]=1;
}
get(belong[l],l,r);
//if(D==2)printf("++ %d %d\n",tou[belong[l]],wei[belong[l]]);
return;
}
else
{
for(int i=l;i<=R[belong[l]];i++)
{
vis[i]=1;
}
get(belong[l],l,R[belong[l]]);
for(int i=L[belong[r]];i<=r;i++)
{
vis[i]=1;
}
get(belong[r],L[belong[r]],r);
for(int i=belong[l]+1;i<belong[r];i++)
{
tou[i]=0;
wei[i]=0;
ma[i]=0;
}
}
}
int query()
{
int tot=0,pos=1;
for(int i=1;i<=sum;i++)
{
if(!tot)pos=L[i];
if(tot+tou[i]>=D)
{
REB(pos);
return pos;
}
if(tou[i]==wei[i]&&tou[i]==R[i]-L[i]+1)
{
tot+=tou[i];
continue;
}
tot=0;//if(D==2)printf("++++++%d\n",i);
if(ma[i]>=D)
{
pos=L[i];
int ci=0;
for(int j=L[i];j<=R[i];j++)
{
if(!vis[j])
{
ci++;
if(ci==D)
{
REB(pos);
return pos;
}
}
else ci=0,pos=j+1;
}
}
pos=R[i]-wei[i]+1,tot=wei[i];
}
return 0;
}
void change()
{
int l=X,r=X+D-1;
if(belong[l]==belong[r])
{ /*if(X==11&&D==5)
printf("++ %d %d\n",l,r);*/
for(int i=l;i<=r;i++)
{
vis[i]=0;
}
get(belong[l],l,r);
}
else
{
for(int i=l;i<=R[belong[l]];i++)
{
vis[i]=0;
}
get(belong[l],l,R[belong[l]]);
for(int i=L[belong[r]];i<=r;i++)
{
vis[i]=0;
}
get(belong[r],L[belong[r]],r);
for(int i=belong[l]+1;i<belong[r];i++)
{
tou[i]=R[i]-L[i]+1;
wei[i]=tou[i];
ma[i]=tou[i];
}
}
}
void iwatch()
{
for(int i=1;i<=sum;i++)
{
printf("%d %d MAX %d\n",tou[i],wei[i],ma[i]);
}
puts("--------------------");
}
int main()
{
freopen("haoi13t4.in","r",stdin);
freopen("haoi13t4.out","w",stdout);
scanf("%d%d",&N,&M);
makeblock();
for(int op,i=1;i<=M;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&D);
printf("%d\n",query());
}
else if(op==2)
{
scanf("%d%d",&X,&D);
change();
}
//if(i>=17)iwatch();
}
//while(1);
fclose(stdin);
fclose(stdout);
return 0;
}
GROWL GOOD BOYส็