BZOJ4216 : Pig
pig
2023-09-11 14:15:04 时间
考虑分块,每块大小为13,则一共需要38465块,求出b[i]表示前i块的和。
查询时中间部分可以$O(1)$查询,只需再往两边累加零散的不超过26个数的和。
空间上一共需要开500000的int和38465的long long。
#include<cstdio> typedef long long ll; const int N=500001,M=38465,K=13; int n,m,t,i,a[N],l,r;ll ans,x,y,b[M]; inline void read(int&a){ char c;bool f=0;a=0; while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-'))); if(c!='-')a=c-'0';else f=1; while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0'; if(f)a=-a; } inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline int pos(int x){return(x-1)/K+1;} inline void ask(int l,int r){ if(pos(l)==pos(r)){ for(i=l;i<=r;i++)ans+=a[i]; return; } ans=b[pos(r)-1]-b[pos(l)]; for(i=l;pos(i)==pos(l);i++)ans+=a[i]; for(i=r;pos(i)==pos(r);i--)ans+=a[i]; } int main(){ read(n),read(m),read(t); for(i=1;i<=n;i++)read(a[i]),b[pos(i)]+=a[i]; for(i=2;i<=pos(n);i++)b[i]+=b[i-1]; while(m--){ if(ans<0)ans=-ans; read(x),read(y); if(t)l=(x^ans)%n+1,r=(y^ans)%n+1;else l=x,r=y; if(l>r)i=l,l=r,r=i; ans=0,ask(l,r); printf("%lld\n",ans); } return 0; }
相关文章
- [Hadoop]转载-Pig的简单介绍
- Apache Pig简介与实践
- Hadoop生态上几个技术的关系与区别:hive、pig、hbase 关系与区别 Pig
- Hadoop生态上几个技术的关系与区别:hive、pig、hbase 关系与区别 Pig
- Hadoop生态上几个技术的关系与区别:hive、pig、hbase 关系与区别 Pig
- Hadoop生态上几个技术的关系与区别:hive、pig、hbase 关系与区别 Pig
- 【25.64%】【codeforces 570E】Pig and Palindromes
- pig—WordCount analysis
- 粉红猪小妹peppa pig中英文版209集+218本绘本+音频
- pig 调试(explain&illerstrate)
- [hadoop系列]Pig的安装和简单演示样例
- 大数据分析处理框架——离线分析(hive,pig,spark)、近似实时分析(Impala)和实时分析(storm、spark streaming)
- 大数据Hadoop之——数据分析引擎Apache Pig