首页 > 代码库 > hdu 5239 Doom
hdu 5239 Doom
题意：给n个数，每次查询[l,r]的和，然后[l,r]之间的数都会由ai变为ai^2,开始计数器为0，每次在上一次的基础上，为计数器+sum[l,r],答案%9223372034707292160
分析：猜想一个数的平方%p应该会很快进入静止，即ai^2%p=ai，这样这个数就不会更新，用java跑了一发，发现最多更新29次，其实这个无所谓，猜想到这个性质就可以了，然后就是解决下一个问题，mod^2很大，long long也存不下，解决了这个问题，我想剩下的就很简单了，a*a=a个a相加，使用类似于快速幂的形式，求a个a相加并对mod取模的值，用一个lay[rt]表示该节点代表的子树不会被更新，这样就Ok了，裸的线段树
#include<bits/stdc++.h>#define mmid int mid=(l+r)>>1#define lson rt*2#define rson rt*2+1using namespace std;typedef long long ll;const ll mod=9223372034707292160LL;const int maxn=1e5+5;ll sum[maxn<<2];bool lay[maxn<<2];int ql,qr;inline bool isdight(char c){return c>=‘0‘&&c<=‘9‘;}void read(ll &res){ char c=getchar(); res=0; while(!isdight(c))c=getchar(); while(isdight(c))res=res*10+c-‘0‘,c=getchar();}void read(int &res){ char c=getchar(); res=0; while(!isdight(c))c=getchar(); while(isdight(c))res=res*10+c-‘0‘,c=getchar();}inline void Mod(ll &x){if(x>=mod)x%=mod;}void build(int rt,int l,int r){ lay[rt]=0; if(l==r){ read(sum[rt]);//scanf("%lld",sum+rt); return ; } mmid; build(lson,l,mid); build(rson,mid+1,r); sum[rt]=(sum[lson]+sum[rson]);Mod(sum[rt]);}ll pow_add(ll a){ ll res=0,t=a,k=a; while(k){ if(k&1)res=(t+res),Mod(res); t=(t+t);Mod(t); k=k>>1; } return res;}ll query(int rt,int l,int r){ if(ql<=l&&qr>=r)return sum[rt]; mmid; ll res=0; if(ql<=mid)res=(res+query(lson,l,mid)),Mod(res); if(qr>mid)res=(res+query(rson,mid+1,r)),Mod(res); return res;}void modify(int rt,int l,int r){ if(lay[rt])return ; if(l==r){ ll t=pow_add(sum[rt]); if(t==sum[rt])lay[rt]=1; else sum[rt]=t; return ; } mmid; if(ql<=mid&&!lay[lson])modify(lson,l,mid); if(qr>mid&&!lay[rson])modify(rson,mid+1,r); lay[rt]=(lay[lson]|lay[rson]); sum[rt]=(sum[lson]+sum[rson]);Mod(sum[rt]);}int main(){ int t,n,q,cas=1,l,r; read(t); while(t--){ read(n);read(q); build(1,1,n); printf("Case #%d:\n",cas++); ll s=0; while(q--){ read(ql);read(qr); s=(s+query(1,1,n));Mod(s); printf("%lld\n",s); modify(1,1,n); } } return 0;}
hdu 5239 Doom
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。