题目链接 点此跳转
题意：单点修改，每次询问输入x，求包含x的最长连续区间
分析：直接暴力分块（相当于三层的树），时间复杂度O(n*sqrt(n) )
坑点：多组输入
Time：390ms
Memory：1792kB
AC代码
#include<bits/stdc++.h>
using namespace std;///hdu 1540 暴力分块
const int N=50005;
struct node
{
int l,r,v;
};
node bk[N];///block 相当于根号n叉树
int bl[N],a[N],tot,ans; ///bl[] belong,表示属于哪个块，a[]就是单个结点
stack<int> sta; ///储存最后一次“毁灭”
int size,n,m;
int read()///快读
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch) )
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch) )
{
x=10*x+ch-'0';
ch=getchar();
}
return x*f;
}
void init()///分块
{
while(!sta.empty() ) sta.pop();
size=sqrt(n);
tot=n/size;
for(int i=1;i<=n;i++)
{
a[i]=1;
bl[i]=(i-1)/size+1;
}
for(int i=1;i<=tot;i++)
{
bk[i].l=(i-1)*size+1;
bk[i].r=i*size;
bk[i].v=size;
}
if(tot*size<n)
{
bk[++tot].l=(tot-1)*size+1;
bk[tot].r=n;
bk[tot].v=n-bk[tot].l+1;
}
}
void query(int x)
{
int t=bl[x];
int t1=x,t2=x-1;
while(t1<=bk[t].r&&a[t1] ) ans++,t1++;///计算当前块
while(t2>=bk[t].l&&a[t2] ) ans++,t2--;
if(t1>bk[t].r)///向外拓展
{
t1=t+1;
while(t1<=tot&&bk[t1].v==bk[t1].r-bk[t1].l+1) ans+=bk[t1++].v;///整块整块的算
if(t1<=tot)///整块的算完了，开始算单个的连续的结点
{
int i=bk[t1].l;
while(i<=bk[t1].r&&a[i] ) ans++,i++;
}
}
if(t2<bk[t].l)
{
t2=t-1;
while(t2>=1&&bk[t2].v==bk[t2].r-bk[t2].l+1) ans+=bk[t2--].v;
if(t2>=1)
{
int i=bk[t2].r;
while(i>=bk[t2].l&&a[i] ) ans++,i--;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
while(m--)
{
char cmd[5];
scanf("%s",cmd);
if(cmd[0]=='D')
{
int x=read();
int t=bl[x];
if(a[x])
bk[t].v--;
a[x]=0;
sta.push(x);
}
else if(cmd[0]=='Q')
{
int x=read();
ans=0;
if(a[x]) query(x);
printf("%d
",ans);
}
else if(!sta.empty() )
{
int x=sta.top();///取最后一次毁灭命令
sta.pop();
a[x]=1;
int t=bl[x];
bk[t].v++;
}
}
}
return 0;
}