AK（线段树/分块）

AK
【问题描述】
NOIPOIPOIP考场上 ，马里奥 顺利地切掉了前两题，他只要再最后一就可以 AK 了。最后一题是这样的：给你个数字序列， 每次查询段区间和了。最后一题是这样的：给你个数字序列， 每次查询段区间和了。最后一题是这样的：给你个数字序列， 每次查询段区间和了。最后一题是这样的：给你个数字序列， 每次查询段区间和了。最后一题是这样的：给你个数字序列， 每次查询段区间和了。最后一题是这样的：给你个数字序列， 每次查询段区间和并且把它们都变成原来的平方。马里奥瞬间就切掉了这道题，但他觉得对 并且把它们都变成原来的平方。马里奥瞬间就切掉了这道题，但他觉得对 并且把它们都变成原来的平方。马里奥瞬间就切掉了这道题，但他觉得对 于别人来说太难了。出题在和马里奥商量后，决定询问时只要求返回模 于别人来说太难了。出题在和马里奥商量后，决定询问时只要求返回模 于别人来说太难了。出题在和马里奥商量后，决定询问时只要求返回模 一个 数 c = 2305843008676823040 的结果。作为另一名NOIP选手的你也已经切掉了 选手的你也已经切掉了 前两题，你能够解决这个修改后的问顺利 AK 吗？
【输入格式】
第一行 两个整数 n,m ，表示 数字 个数 和询问个数 。
接下来 一行 n个数字 ai ，表示 序列的 初始值。
接下 来 m行，每两个整数 l,r 表示询问区间 。
【输出格式】
对于每次询问，你需要输出一个整数表示应的结果。

这题线段树啊分块都行
主要是模数上做了手脚，就是说当一个数平方六十次左右的时候就会开始循环了（1000000以内只要28次），所以……又是优化暴力。

线段树

#include 
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
using namespace std;
typedef unsigned long long ll;
const ll mod =2305843008676823040uLL; 
const int maxn=100500;int n,m;
ll ans,val[maxn];struct tree{int left,right,flag;ll val;
}tree[maxn<<2];
inline ll mul(ll x,ll y)
{ll res=0;while(y){if(y&1) res=(res+x)%mod;y>>=1;x=x*2%mod;}return res;
}
inline void build(int left,int right,int cur)
{tree[cur].left=left;tree[cur].right=right;tree[cur].flag=0;if(left==right){tree[cur].val=val[left];return;}int mid=(left+right)>>1;build(left,mid,(cur<<1));build(mid+1,right,(cur<<1)|1);tree[cur].val=tree[(cur<<1)].val+tree[((cur<<1)|1)].val;
}inline void query(int a,int b,int cur)
{int left=tree[cur].left;int right=tree[cur].right;if(a==left && b==right && tree[cur].flag==1) { ans=(ans+tree[cur].val)%mod;return ;}if(left==right){ans=(ans+tree[cur].val)%mod;ll tmp=mul(tree[cur].val,tree[cur].val);if(tmp==tree[cur].val){ tree[cur].flag=1;}tree[cur].val=tmp;return ;}int mid=(left+right)>>1;if(b<=mid) query(a,b,(cur<<1));else if(a>mid) query(a,b,((cur<<1)|1));else {query(a,mid,(cur<<1));query(mid+1,b,((cur<<1)|1));}tree[cur].val=(tree[(cur<<1)].val+tree[((cur<<1)|1)].val)%mod;if(tree[cur<<1].flag && tree[(cur<<1)|1].flag ) tree[cur].flag=1;
}int main()
{//freopen("ak.in","r",stdin);//freopen("ak.out","w",stdout); scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%I64u",&val[i]);build(1,n,1);for(int i=0;i<m;i++) {int a,b;scanf("%d%d",&a,&b);ans=0;query(a,b,1);ans%=mod;printf("%I64u\n",ans);}return 0;
}

分块

# include 
# define int long long
# define Rint register long long 
using namespace std;
const int mo=2305843008676823040,E=30,MAXN=(2<<16)+1;
int n,m,bl;
int f[MAXN],L[MAXN],R[MAXN],sum[MAXN],cnt[MAXN];
struct rec{int bl,val;
}a[MAXN];
inline int read()
{int X=0,w=0; char c=0;while(c<'0'||c>'9') {w|=c=='-';c=getchar();}while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();return w?-X:X;
}
inline void print(Rint x)
{if(x>9) print(x/10);putchar(x%10+'0');
}
inline int father(Rint x)
{if (f[x]==x) return f[x];f[x]=father(f[x]);return f[x]; 
}
inline int mul(Rint a,Rint b)
{int res=0ll;while (b) {if (b&1) res=(res+a)%mo;a=(a<<1)%mo; b>>=1;}return res%mo;
}
inline int solve(Rint l,Rint r)
{int lb=a[l].bl,rb=a[r].bl,ans=0ll;if (lb==rb) {for (Rint i=l;i<=r;i++) ans=(ans+a[i].val)%mo;return ans;}for (Rint i=l;i<=R[lb];i++) ans=(ans+a[i].val)%mo;for (Rint i=r;i>=L[rb];i--) ans=(ans+a[i].val)%mo;for (Rint i=lb+1;i<=rb-1;i++) ans=(ans+sum[i])%mo; return ans%mo;
}
inline void update(Rint l,Rint r)
{for (Rint i=l;i<=r;i=father(i+1)) {if (i>r||i==0) break; int nowbl=a[i].bl;sum[nowbl]=(sum[nowbl]-a[i].val+mo)%mo;a[i].val=mul(a[i].val,a[i].val)%mo; cnt[i]++;if (cnt[i]>E) f[i]=father(i+1);sum[nowbl]=(sum[nowbl]+a[i].val)%mo;}
}
signed main()
{freopen("ak.in","r",stdin);freopen("ak.out","w",stdout);scanf("%lld%lld",&n,&m); for (Rint i=1;i<=n;i++) f[i]=i;memset(cnt,0,sizeof(cnt));bl=1; L[1]=1;int POA=sqrt(n)+1;for (Rint i=1;i<=n;i++)  {if (i%POA==0) { R[bl]=i-1; bl++; L[bl]=i; }a[i].val=read();a[i].bl=bl;sum[bl]=(sum[bl]+a[i].val)%mo;} R[bl]=n;Rint l,r; while (m--)  {l=read();r=read();print(solve(l,r)); putchar('\n');update(l,r);} return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！