CDOJ 1324 卿学姐与公主 分块

题目地址

分块模板

 #include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
const int Nmax=;
int num,block,l[Nmax],r[Nmax],n,q,belong[Nmax];
long long Max[Nmax],a[Nmax]; void build()
{
block=sqrt(n);
num=n/block;
if(n%block) num++;
for(int i=;i<=n;i++)
{
l[i]=(i-)*block+;
r[i]=i*block;
belong[i]=(i-)/block+;
}
r[num]=n; for(int i=;i<=n;i++)
a[i]=; for(int i=;i<=num;i++)
for(int j=l[i];j<=r[i];j++)
Max[j]=max(Max[j],a[j]);
} void update(int x,int data)
{
a[x]+=data;
Max[belong[x]]=max(Max[belong[x]],a[x]);
} long long ask(int x,int y)
{
long long ans=;
if(belong[x]==belong[y])
{
for(int i=x;i<=y;i++)
{
ans=max(ans,a[i]);
}
return ans;
}
for(int i=x;i<=r[x];i++)
ans=max(ans,a[i]);
for(int i=belong[x]+;i<belong[y];i++)
ans=max(ans,Max[i]);
for(int i=l[y];i<=y;i++)
ans=max(ans,a[i]);
return ans;
} int main()
{
scanf("%d%d",&n,&q);
while(q--)
{
int c,x,y;
scanf("%d%d%d",&c,&x,&y);
if(c==)
update(x,y);
else
printf("%lld\n",ask(x,y));
}
return ;
}
上一篇:maven中解决javax.servlet.jsp.PageContext cannot be resolved to a type


下一篇:mysql 备份和还原