BNU 12680 Jupiter Atacks! (线段树)

题意：给定一个区间，，两种操作，一种是将x的值赋为y，另一种为询问区间（x，y）的sum值，此处sum值的运算为：

H(fi,..., fj) = Bkfj-k ( mod P)

例如： H(f2,..., f5) = B^0 * f5 + B^1 * f4 + B^2 * f3 + B^3 * f2 ( mod P)

这题隐藏的好深~~~ 用线段树的话，用va域存储树内所有的H（tr[x].l，tr[x].r），更新时根据更新点和区间右端点乘以个（B ^ (tr[x].r - pos)）,求和时根据求和区间右端点和线段树区间的右端点乘以个（B ^( r - tr[x].r））。

需要注意的是，取余过程中可能会产生负数，需要归正。

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include<functional>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <climits>//形如INT_MAX一类的  
#define MAX 100050  
#define INF 0x7FFFFFFF  
#define L(x) x<<1  
#define R(x) x<<1|1  
using namespace std;  
  
int b,p,l,n;  
long long B[MAX],ans;  
int a[MAX];  
struct node {  
    int l,r,mid;  
    long long va;  
}tr[MAX * 4];  
  
void init() {  
    memset(a,0,sizeof(a));  
    B[0] = 1;  
    for(int i=1; i<=l; i++) {  
        B[i] = (B[i - 1] * b) % p;  
    }  
}  
  
void build(int l,int r,int x) {  
    tr[x].l = l;  
    tr[x].r = r;  
    tr[x].mid = (l + r) >> 1;  
    tr[x].va = 0;  
    if(l == r) return ;  
    build(l,tr[x].mid,L(x)) ;  
    build(tr[x].mid + 1, r, R(x));  
}  
  
void update(int l,int x,int va) {  
    tr[x].va = (tr[x].va + B[tr[x].r - l] * va % p ) % p;  
    if(tr[x].va < 0) tr[x].va += p;  
    if(tr[x].l == tr[x].r) return ;  
    if(l > tr[x].mid) update(l,R(x),va);  
    else update(l,L(x),va);  
}  
  
void query(int l,int r,int x) {  
    if(l <= tr[x].l && r >= tr[x].r) {  
        ans = (ans + B[r - tr[x].r] * tr[x].va % p) % p;  
        if(ans < 0) ans += p;  
        return ;  
    }  
    if(r > tr[x].mid) query(l,r,R(x));  
    if(l <= tr[x].mid) query(l,r,L(x));  
}  
  
void test() {  
    for(int i=0; i<=3 * l; i++) {  
        printf("%d %d %lld\n",tr[i].l,tr[i].r,tr[i].va);  
    }  
}  
  
int main() {  
    while(scanf("%d%d%d%d",&b,&p,&l,&n)) {  
        if(b == 0 && p == 0 && l == 0 && n == 0) break;  
        char op;  
        int x,y;  
        init();  
        build(1,l,1);  
        for(int i=0; i<n; i++) {  
            getchar();  
            scanf("%c%d%d", &op,&x,&y);  
            if(op == 'E') {  
                update(x,1,y - a[x]);  
                a[x] = y;  
            } else {  
                ans = 0;  
                //test();  
                query(x,y,1);  
                printf("%lld\n",ans);  
            }  
        }  
        puts("-");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,