HDU - 1166 敌兵布阵 （分块）

/**
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
考虑是否用莫队或者分块 主要还是看数据范围吧
一般是<=1e5
单点修改+区间查询
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
/**********************************************Head-----Template****************************************/
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){ll gg=gcd(a,b);a/=gg;if(a<=LLONG_MAX/b) return a*b;return LLONG_MAX;}
/********************************Head----Temlate**********************************************/
const int maxn=1e5+7;
int n,m;
ll tmp[maxn];
int tag[maxn],s[maxn],pos[maxn];
ll query(int l,int r){
ll ans=0;
for(int i=l;i<=min(r,pos[l]*m);i++) ans+=s[i]+tag[pos[l]];
if(pos[l]!=pos[r]){
for(int i=(pos[r]-1)*m+1;i<=r;i++) ans+=s[i]+tag[pos[r]];
}
for(int i=pos[l]+1;i<=pos[r]-1;i++) ans+=tmp[i];
return ans;
}
void add(int id,int val){
for(int i=(pos[id]-1)*m+1;i<=min(pos[id]*m,n);i++){
s[i]+=tag[pos[id]];
if(i==id) s[i]+=val;
}
tag[pos[id]]=0;tmp[pos[id]]+=val;
}
void solved(){
int t;read(t);
for(int cas=1;cas<=t;cas++){
memset(tmp,0,sizeof(tmp));
memset(tag,0,sizeof(tag));
read(n);m=sqrt(n);
for(int i=1;i<=n;i++) read(s[i]),pos[i]=(i-1)/m+1;
for(int i=1;i<=n;i++) tmp[pos[i]]+=s[i];
char str[10];
printf("Case %d:n",cas);
while(~scanf("%s",str)){
if(strcmp(str,"End")==0) break;
int l,r;read(l),read(r);
if(str[0]=='Q') writeln(query(l,r));
else if(str[0]=='A') add(l,r);
else if(str[0]=='S') add(l,-r);
}
}
}
int main(){
solved();
return 0;
}

最后

以上就是爱笑茉莉为你收集整理的HDU - 1166 敌兵布阵 （分块）的全部内容，希望文章能够帮你解决HDU - 1166 敌兵布阵 （分块）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。