当前位置 博文首页 > ttoobne:线段树yy (线段树维护等比数列的和)
没有题目链接
一个长度为 n 的序列,Q 次操作:
对于所有操作,b 不变。(1 <= n, Q <= 1e5, 1 < b <= 1e9)
题解:
由于每次加的是一个等比数列,那么可以将等比数列的首项作为下传标记更新。
由于没有交题的地方,就自己写了个对拍程序QAQ,和一位大佬的代码对拍。(附上源代码和对拍程序,如有错误欢迎指出)
对拍结果 100% 的代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int ll
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair<int, int>
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int mod = 1e9 + 7;
const int M = 1000000 + 10;
const int N = 100000 + 10;
long long mulmod(long long n, long long m)
{
n %= mod, m %= mod;
return (n * m - (long long)((long double)n / mod * m) * mod + mod) % mod;
}
int powmod(int n, int m)
{
int ans = 1;
while(m) {
if(m & 1) ans = mulmod(ans, n) % mod;
n = mulmod(n, n) % mod;
m >>= 1;
}
return ans % mod;
}
int n, q, b;
int tree[N<<2], add[N<<2];
int pow_q[N], inv;
int sum(int a1, int num)
{
return mulmod(mulmod(a1, (pow_q[num] - 1)), inv);
}
void build(int l = 1, int r = n, int rt = 1)
{
if(l == r) {
scanf("%lld", &tree[rt]);
return ;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod;
}
void push(int l, int r, int rt)
{
if(add[rt]) {
int mid = (l + r) >> 1, temp;
add[rt << 1] = (add[rt << 1] + add[rt]) % mod;
add[rt << 1 | 1] = (add[rt << 1 | 1] + (temp = add[rt] * pow_q[mid - l + 1] % mod)) % mod;
tree[rt << 1] = (tree[rt << 1] + sum(add[rt], mid - l + 1)) % mod;
tree[rt << 1 | 1] = (tree[rt << 1 | 1] + sum(temp, r - mid)) % mod;
add[rt] = 0;
}
}
void update(int L, int R, int l = 1, int r = n, int rt = 1)
{
if(L <= l && r <= R) {
int a1 = pow_q[l - L];
tree[rt] = (tree[rt] + sum(a1, r - l + 1)) % mod;
add[rt] += a1;
return ;
}
push(l, r, rt);
int mid = (l + r) >> 1;
if(L <= mid) update(L, R, l, mid, rt << 1);
if(mid < R) update(L, R, mid + 1, r, rt << 1 | 1);
tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod;
}
int query(int L, int R, int l = 1, int r = n, int rt = 1)
{
if(L <= l && r <= R) return tree[rt];
push(l, r, rt);
int mid = (l + r) >> 1, ans = 0;
if(L <= mid) ans = (ans + query(L, R, l, mid, rt << 1)) % mod;
if(mid < R) ans = (ans + query(L, R, mid + 1, r, rt << 1 | 1)) % mod;
return ans;
}
void pre()
{
inv = powmod(b - 1, mod - 2);
pow_q[0] = 1;
for(int i = 1; i <= n; i ++) {
pow_q[i] = pow_q[i - 1] * b % mod;
}
build();
}
signed main()
{
freopen("in.in", "r", stdin);
freopen("txb.out", "w", stdout);
scanf("%lld %lld %lld", &n, &q, &b);
pre();