2016 UESTC Training for Data Structures O – 卿学姐种美丽的花 树状数组+等差数列

Source

2016 UESTC Training for Data Structures  Problem O

My Solution

树状数组+等差数列

更的时候 Ax = A0 + (x-x0)*(-1)

所以Ax求和并加上初始值就是新的val[x]了，这个最后加上初始值直接输出就行

sum(Ax) = sum(A0+x0) - sum(x更新的次数)

然后A0 + x0用一个树状数组维护，在更新点add(x0, A0+x0); 并在更新结尾的地方 add(x0+y0, -(x0+y0)),

这样用树状数组地方get()的时候就不会对后面没有更新到的地方有影响了

用另一个数组维护x出现的次数，在更新点add(x0, 1); 并在更新结尾的地方 add(x0+y0, -1), 同理对后面没有影响了

复杂度 O(q*logn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 +8;
//!A0 = sum(A0 + (x-x0)*(-1) ); ==> Ax = sum(A0+x0) - sum(x被更新的次数)
LL Tree[maxn], Tree2[maxn];   //Tree 记录 sum( )  Tree 记录 x 被更新的次数
int n, val[maxn];

inline int lowbit(int x)
{
    return (x&-x);
}

void add(int x, int value)
{
    for(int i = x; i <= n; i+= lowbit(i))
        Tree[i] += value;
}

LL get(int x)
{
    LL sum = 0;
    for(int i = x;i;i-=lowbit(i))
        sum+=Tree[i];
    return (sum);
}

//Tree2
void add2(int x, int value)
{
    for(int i = x; i <= n; i+= lowbit(i))
        Tree2[i] += value;
}

LL get2(int x)
{
    LL sum = 0;
    for(int i = x;i;i-=lowbit(i))
        sum+=Tree2[i];
    return (sum);
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int q;
    memset(Tree, 0, sizeof Tree);
    memset(Tree2, 0, sizeof Tree2);
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++){
        scanf("%d", &val[i]);
    }
    int op, x, y;
    while(q--){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d", &x, &y);
            add(x, x+y);
            if(x+y <= n) add(x+y, -(x+y));     //!在更新的结尾处加上个 - (x+y) 这样对后面没有更新到的地方就没有影响了 后面都抵消为 0 了
            add2(x, 1);
            if(x+y <= n) add2(x+y, -1);        //!在更新的结尾处加上个 - 1 这样对后面没有更新到的地方就没有影响了 后面都抵消为 0 了
        }
        else{
            scanf("%d", &x);
            //t = -get(x-1);
            LL ans = get(x) - x*get2(x) + val[x];
            printf("%dn", int( ans % (772002+233)));  //get(0) == 0
        }
    }

    return 0;

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx