首页 > 代码库 > 【BZOJ4869】相逢是问候 [线段树]
【BZOJ4869】相逢是问候 [线段树]
相逢是问候
Time Limit: 40 Sec Memory Limit: 512 MB[Submit][Status][Discuss]
Description
Informatikverbindetdichundmich.
信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以
分为两种：0 l r表示将第l个到第r个数（al,al+1,...,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是
输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为
这个结果可能会很大，所以你只需要输出结果mod p的值即可。
Input
第一行有三个整数n,m,p,c，所有整数含义见问题描述。
接下来一行n个整数，表示a数组的初始值。
接下来m行，每行三个整数，其中第一个整数表示了操作的类型。
如果是0的话，表示这是一个修改操作，操作的参数为l,r。
如果是1的话，表示这是一个询问操作，操作的参数为l,r。
Output
对于每个询问操作，输出一行，包括一个整数表示答案mod p的值。
Sample Input
4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3
Sample Output
0
3
3
HINT
1 ≤ n ≤ 50000, 1 ≤ m ≤ 50000, 1 ≤ p ≤ 100000000, 0 < c <p, 0 ≤ ai < p
Solution
首先，我们运用欧拉定理：
然后还有一个定理：一个数在执行log次操作后，值不会改变。
于是乎，我们可以运用线段树，暴力修改每一个值，如果值都不变了则不修改。
然后我们再考虑一下，怎么修改这个值：
已知a(原值)和times(修改次数)，我们考虑每一次%什么，
考虑每一次b的模数。
首先如果b%phi(p)，意味着a^b在%p下同余。
如果这一次b%phi(phi(p))，意味着a^b在phi(p)下同余，
同时也意味着下一次在%phi(p)意义下。
我们要让答案最后是在%p意义下的，那么显然每次b%phi[times-1]。
再带上快速幂，那么这样效率就是O(nlog^3(n))的。
Code
#include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib>#include<cmath>using namespace std; typedef long long s64;const int ONE = 500005;const int INF = 2147483640;int n,m,p,C;int opt,x,y;int a[ONE],phi[ONE],p_num;int MOD;int res;struct power{ int value; int cnt;}Node[ONE];int get(){ int res=1,Q=1;char c; while( (c=getchar())<48 || c>57 ) if(c==‘-‘)Q=-1; res=c-48; while( (c=getchar())>=48 && c<=57 ) res=res*10+c-48; return res*Q;}int Getphi(int n){ int res = n; for(int i=2; i*i<=n; i++) if(n % i == 0) { res = res/i*(i-1); while(n % i == 0) n /= i; } if(n != 1) res = res/n*(n-1); return res;}int Quickpow(int a,int b,int MOD){ int res = 1; while(b) { if(b & 1) res = (s64)res * a % MOD; a = (s64)a * a % MOD; b >>= 1; } return res;}void Build(int i,int l,int r){ if(l == r) { Node[i].value = a[l] % MOD; return; } int mid = l+r>>1; Build(i<<1, l, mid); Build(i<<1|1, mid + 1, r); Node[i].value = (Node[i<<1].value + Node[i<<1|1].value) % MOD;}int Calc(int a, int times){ for(int i=times; i>=1; i--) { if(a >= phi[i]) a = a%phi[i] + phi[i]; a = Quickpow(C, a, phi[i-1]); if(!a) a = phi[i-1]; } return a;}void Update(int i,int l,int r,int L,int R){ if(Node[i].cnt >= p_num) return; if(l == r) { Node[i].value = Calc(a[l], ++Node[i].cnt); return; } int mid = l+r>>1; if(L <= mid) Update(i<<1, l, mid, L, R); if(mid+1 <= R) Update(i<<1|1, mid+1, r, L, R); Node[i].value = (Node[i<<1].value + Node[i<<1|1].value) % MOD; Node[i].cnt = min(Node[i<<1].cnt, Node[i<<1|1].cnt);}void Query(int i,int l,int r,int L,int R){ if(L<=l && r<=R) { res = (res + Node[i].value) % MOD; return; } int mid = l+r>>1; if(L <= mid) Query(i<<1, l, mid, L, R); if(mid+1 <= R) Query(i<<1|1, mid+1, r, L, R);}int main(){ n = get(); m = get(); p = get(); C = get(); for(int i=1; i<=n; i++) a[i] = get(); MOD = phi[0] = p; while(p!=1) phi[++p_num] = p = Getphi(p); phi[++p_num] = 1; Build(1, 1, n); while(m--) { opt = get(); x = get(); y = get(); if(!opt) Update(1, 1, n, x, y); else { res = 0; Query(1, 1, n, x, y); printf("%d\n", res); } }}
【BZOJ4869】相逢是问候 [线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。