# 【bzoj2962】序列操作 线段树

5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1

40

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
#define mod 19940417
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
typedef long long ll;
ll add[N << 2] , c[N][21];
int rev[N << 2];
char str[5];
struct data
{
ll v[21] , si;
data() {memset(v , 0 , sizeof(v)) , v[0] = si = 1;}
ll &operator[](int a) {return v[a];}
data operator+(data a)
{
data ans;
int i , j;
ans.si = si + a.si;
for(i = 1 ; i <= 20 ; i ++ )
for(j = 0 ; j <= i ; j ++ )
ans[i] = (ans[i] + v[j] * a[i - j]) % mod;
return ans;
}
data operator+(ll a)
{
data ans;
int i , j;
ll t;
ans.si = si;
for(i = 1 ; i <= 20 ; i ++ )
for(t = 1 , j = 0 ; j <= i ; j ++ , t = t * a % mod)
ans[i] = (ans[i] + v[i - j] * t % mod * c[si - i + j][j]) % mod;
return ans;
}
data operator-()
{
data ans = *this;
int i;
for(i = 1 ; i <= 20 ; i += 2) ans[i] = (mod - ans[i]) % mod;
return ans;
}
}a[N << 2];
inline void pushup(int x)
{
a[x] = a[x << 1] + a[x << 1 | 1];
}
inline void pushdown(int x)
{
if(rev[x])
{
a[x << 1] = -a[x << 1] , a[x << 1 | 1] = -a[x << 1 | 1];
add[x << 1] = (mod - add[x << 1]) % mod , add[x << 1 | 1] = (mod - add[x << 1 | 1]) % mod;
rev[x << 1] ^= 1 , rev[x << 1 | 1] ^= 1;
rev[x] = 0;
}
{
a[x << 1] = a[x << 1] + add[x] , a[x << 1 | 1] = a[x << 1 | 1] + add[x];
}
}
void build(int l , int r , int x)
{
if(l == r)
{
scanf("%lld" , &a[x][1]) , a[x][1] = (a[x][1] % mod + mod) % mod;
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
pushup(x);
}
void update(int b , int e , ll v , int l , int r , int x)
{
if(b <= l && r <= e)
{
a[x] = a[x] + v , add[x] = (add[x] + v) % mod;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , v , lson);
if(e > mid) update(b , e , v , rson);
pushup(x);
}
void reverse(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e)
{
a[x] = -a[x] , add[x] = (mod - add[x]) % mod , rev[x] ^= 1;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(b <= mid) reverse(b , e , lson);
if(e > mid) reverse(b , e , rson);
pushup(x);
}
data query(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e) return a[x];
pushdown(x);
int mid = (l + r) >> 1;
if(e <= mid) return query(b , e , lson);
else if(b > mid) return query(b , e , rson);
else return query(b , e , lson) + query(b , e , rson);
}
void init(int n)
{
int i , j;
c[0][0] = 1;
for(i = 1 ; i <= n ; i ++ )
{
c[i][0] = 1;
for(j = 1 ; j <= 20 ; j ++ )
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
int main()
{
int n , m , x , y , z;
scanf("%d%d" , &n , &m);
init(n) , build(1 , n , 1);
while(m -- )
{
scanf("%s%d%d" , str , &x , &y);
if(str[0] == ‘I‘) scanf("%d" , &z) , update(x , y , (z % mod + mod) % mod , 1 , n , 1);
else if(str[0] == ‘R‘) reverse(x , y , 1 , n , 1);
else scanf("%d" , &z) , printf("%lld\n" , query(x , y , 1 , n , 1)[z]);
}
return 0;
}


【bzoj2962】序列操作 线段树

(0)
(0)

0条