UESTC 1581 Rikka的烦恼 分块、线段树

Rikka的烦恼 分块、线段树

Source

17暑假前集训-数据结构专题 By AutSky_JadeK

2017 UESTC Training for Data Structures

UESTC 1581 Rikka的烦恼

My Solution

题意：给出一个序列，询问某一段下标是等差数列的子序列的最大值。每次询问给出首项和公差。
每次单点修改。

分块、线段树
由于 7e4*7e4 == 4.9e9,所以如果除以10的话，4.9e8，大致可以满足1ms == 1e9次运算，
所以设定一个阈值，公比大于k的时候，直接算出最大值，
公比小于k的时候用O(k^2)棵线段树维护，tree[i-1][j]表示以i为公比j为首项的线段树。
所以先预处理出线段树，
然后每次询问根据k的不同，分别直接处理或者用线段树维护。
复杂度 O(n^2/k)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const LL MAXN = 7e4 + 8; //前面用 (7e4)/6 + 8; RE了
const LL INF = -9e18 - 8;
const int K = 6;

LL val[MAXN];
struct Tree{
    LL top[4*MAXN], findans;
    int sz;
    void pushup(int Ind){
        top[Ind] = max(top[Ind<<1], top[Ind<<1|1]); } void _Modify(int a, int l, int r, int Ind, LL d){ if(l == r && r == a){ top[Ind] += d; return; } int mid = (l + r) >> 1;
        if(a <= mid) _Modify(a, l, mid, Ind<<1, d);
        else _Modify(a, mid+1, r, Ind<<1|1, d);
        pushup(Ind);
    }
    void _Query(int a, int b, int l, int r, int Ind){
        if(a <= l && r <= b){ if(findans == INF){ findans = top[Ind]; } else{ findans = max(findans, top[Ind]); } return; } int mid = (l + r) >> 1;
        if(a <= mid) _Query(a, b, l, mid, Ind<<1); if(b > mid) _Query(a, b, mid+1, r, Ind<<1|1);
        pushup(Ind);
    }
    void Modify(int a, LL d){ _Modify(a, 1, sz, 1, d);}
    void Query(int a, int b){findans = INF; _Query(a, b, 1, sz, 1);}
} tree[K][K];

int main()
{
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);
    LL T = 2;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);


    LL n, m, i, j, k, tot, sz = 9, op, x, y, ans, ptr;
    scanf("%lld", &n);
    for(i = 1; i <= n; i++){
        scanf("%lld", &val[i]);
    }

    for(i = 1; i <= K; i++){
        for(j = 0; j < i; j++){
            tree[i-1][j].sz = (n - j) / i + 1;
            //if((n - j) % i != 0) tree[i-1][j].sz++;
            for(k = 0; k*i + j <= n; k++){
                tree[i-1][j].Modify(k+1, val[k*i + j]);
            }
        }
    }

    scanf("%lld", &m);
    while(m--){
        scanf("%lld%lld%lld", &op, &x, &y);
        if(op == 0){
            val[x] += y;
            for(i = 1; i <= K; i++){
                for(j = 0; j < i; j++){ if((x - j) % i == 0){ k = (x - j) / i; tree[i-1][j].Modify(k+1, y); } } } } else{ if(y > K){
                ans = INF;
                for(k = x; k <= n; k += y){
                    ans = max(ans, val[k]);
                }
            }
            else{
                i = x % y;
                k = x / y;
                tree[y-1][i].Query(k+1, tree[y-1][i].sz);
                ans = tree[y-1][i].findans;
            }
            printf("%lldn", ans);
        }
    }


    #ifdef LOCAL
    memset(tree, 0, sizeof tree);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx