博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
SPOJ GSS1 ~ 8解题报告 【完整版】
阅读量：5243 次
发布时间：2019-06-14

本文共 30285 字，大约阅读时间需要 100 分钟。

若转载请注明出处！！！

GSS1 —— GSS8 简述做法加代码。

GSS1

给出了序列\(A[1]\)，\(A[2]\)，…，\(A[N]\)。 \((a[i]≤15007,1≤N≤50000)\)。查询定义如下： 查询\((x,y)=max\{a[i]+a[i+1]+...+a[j];x≤i≤j≤y\}\)。 给定M个查询，程序必须输出这些查询的结果。

思路：

我们维护四个值：

sum, lsum, rsum, msum

然后进行更新，静态查询即可。

具体讲解见

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 50010#define inf 1 << 30#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...struct tree{    int lsum, rsum, sum, msum;} z[mn << 2];inline void update(int rt){    z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;    z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1].sum + z[rt << 1 | 1].lsum);    z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1 | 1].sum + z[rt << 1].rsum);    z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);}inline void build(int l,int r,int rt){    if(l==r){        z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = read();        return;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    update(rt);}inline tree query(int l,int r,int rt,int nowl,int nowr){    if(nowl<=l && r<=nowr){return z[rt];}    int m = (l + r) >> 1;    bool fl = false, fr = false;    tree tl, tr, res;    if (nowl <= m){        if(m

GSS2

给出 \(n\) 个数，\(q\) 次询问，求最大子段和，相同的数只算一次。

思路：

因为没有修改，我们考虑离线做。

我们把询问 \([l, r]\) 按照 \(r\) 的升序排序，在线段树内维护 \(sum\) 和 它的历史最大值 \(hmax\)，我们可以记 \(pre[i]\) 作为第 \(i\) 个元素的上一个元素的位置。

我们把原数组按读入顺序加入，我们只需要把这个 \(a[i]\) 在区间 \([pre[i] + 1, i]\) 上区间加即可，然后查询时直接查询 \([l, r]\) 的历史最大值。

记得加上维护左右儿子的 \(sum\) 最大值和左右儿子 \(hmax\) 的最大值，这样我们才能更新 本节点的 \(hmax\)。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 100010#define inf 1 << 30#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...struct Que{    ll l, r, id;} q[mn];ll b[mn], ans[mn];ll pre[mn << 1], suf[mn << 1];inline bool cmp(Que a,Que b){    return a.r < b.r;}struct tree{    ll sum, hsum, cols, hcol;};struct SegmentTree{    tree z[mn << 2];    inline tree operation(tree a,tree b){        return (tree){max(a.sum, b.sum), max(a.hsum, b.hsum)};    }    inline void update(int rt){        z[rt].sum = max(z[rt << 1].sum, z[rt << 1 | 1].sum);        z[rt].hsum = max(z[rt << 1].hsum, z[rt << 1 | 1].hsum);    }    inline void color(int l, int r, int rt){        z[rt].hsum = max(z[rt].hsum, z[rt >> 1].hcol + z[rt].sum);        z[rt].sum += z[rt >> 1].cols;        z[rt].hcol = max(z[rt].hcol, z[rt >> 1].hcol + z[rt].cols);        z[rt].cols += z[rt >> 1].cols;    }    inline void coloring(int l,int r,int rt,ll v){        z[rt].sum += v;        z[rt].hsum = max(z[rt].sum, z[rt].hsum);        z[rt].cols += v;        z[rt].hcol = max(z[rt].cols, z[rt].hcol);    }    inline void push_col(int l,int r,int rt){        int m = (l + r) >> 1;        color(lson);        color(rson);        z[rt].hcol = z[rt].cols = 0;    }    inline void modify(int l,int r,int rt,int nowl,int nowr,ll v){        if(nowl<=l && r<=nowr){            coloring(bson,v);            return;        }        int m = (l + r) >> 1;        push_col(bson);        if (nowl <= m)            modify(lson, nowl, nowr, v);        if(m
         
          > 1; push_col(bson); if(nowl<=m){ if(m

GSS3

\(n\) 个数，\(q\) 次操作

  • 0 \(x\) \(y\) 把 \(A_x\) 修改为 \(y\)

  • 1 \(l\) \(r\) 询问区间 \([l, r]\) 的最大子段和

思路

直接在GSS1代码里加上单点加就好，没什么其他注意的。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 100010#define inf 1 << 30#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...struct tree{    int sum, lsum, rsum, msum;} z[mn << 2];inline void update(int rt){    z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;    z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1 | 1].lsum + z[rt << 1].sum);    z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1].rsum + z[rt << 1 | 1].sum);    z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);}inline void build(int l,int r,int rt){    if(l==r){        z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = read();        return;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    update(rt);}inline void modify(int l,int r,int rt,int now,int v){    if(l==r && l==now){        z[rt].sum = z[rt].rsum = z[rt].msum = z[rt].lsum = v;        return;    }    int m = (l + r) >> 1;    //push_col(bson);    if(now<=m)        modify(lson, now, v);    else        modify(rson, now, v);    update(rt);}inline tree query(int l,int r,int rt,int nowl,int nowr){    if(nowl<=l && r<=nowr){        //cout << z[rt].msum << " ";        return z[rt];    }    int m = (l + r) >> 1;    //push_col(bson);    tree tl, tr, res;    if(nowl<=m){        if(m

GSS4

「题意」： \(n\) 个数，和在 \(10 ^ {18}\)

现在有「两种」操作

  • 0 \(x\) \(y\) 把区间 \([x,y]\) 内的每个数开方，下取整

  • 1 \(x\) \(y\) 询问区间 \([x,y]\) 的每个数的和

「格式」： 有多组数据，数据以EOF结束，对于每组数据，输出数据的序号，每组数据之后输出一个空行。

「注意」： 不保证给出的区间 \([x, y]\) 有 \(x <= y\) ，如果 \(x > y\) 请交换\(x\) ，\(y\) 。

思路

如果数据都在 10 ^ 18 那说明我们如果此次开方的话，肯定在很快的几次开方后变成了 1 ，所以，如果这个区间的数字开方开着开着都变成了 1， 那么就没必要在去开方了。经计算，每个数最多开 7 ~ 8 次（保守说的），所以我们直接暴力在线段树上修改最多会修改 8 * N * logN。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 100010#define inf 1 << 30#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline ll read(){    ll f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...ll z[mn << 2];inline void update(int rt){    z[rt] = z[rt << 1] + z[rt << 1 | 1];}inline void build(int l,int r,int rt){    if(l==r){        z[rt] = read();        return;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    update(rt);}inline void modify(int l,int r,int rt,int nowl,int nowr){    if(r-l+1 == z[rt])        return;    if(l==r){        z[rt] = sqrt(z[rt]);        return;    }    int m = (l + r) >> 1;    if(nowl<=m)        modify(lson, nowl, nowr);    if(m
        
         > 1;    if(nowl<=m){        if(m
         
          y) swap(x, y); if(!s){ modify(root, x, y); }else{ printf("%lld\n", query(root, x, y)); } } putchar('\n'); } return 0;}

GSS5

给定一个序列。查询左端点在\([x_1, y_1]\)之间，且右端点在\([x_2, y_2]\)之间的最大子段和，数据保证\(x_1 <= x_2\), \(y_1 <= y_2\)，但是不保证端点所在的区间不重合

思路

我们考虑分类讨论。

首先是\(y_1 <= x_2\)的情况，这种情况说明，\([y_1, x_2]\)必定在答案的和之中，我们要求的就是\([x_1, y_1]\)的最大后缀和，加上\([x_2, y_2]\)的最大前缀和，加上\([y_1, x_2]\)的区间和。

然后就是一个比较麻烦的情况，\(y_1 > x_2\)。

这种情况可能有三种最佳答案。一种是以 \(y_1\) 为分界的最大后缀和（区间\([x_1, y_1]\)）与最大前缀和（\([y_1, y_2]\)），一种是以 \(x_2\) 为分界的最大后缀和（\([x_1, x_2]\)）与最大前缀和（\([x_2, y_2]\)），第三种就是所取答案都在 \([x_2, y_1]\) 中。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 50010#define inf 1 << 30#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...struct tree{    int lsum, rsum, sum, msum;} z[mn << 2];int a[mn];inline void update(int rt){    z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;    z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1].sum + z[rt << 1 | 1].lsum);    z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1 | 1].sum + z[rt << 1].rsum);    z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);}inline void build(int l,int r,int rt){    if(l==r){        z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = a[l];        return;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    update(rt);}inline tree query(int l,int r,int rt,int nowl,int nowr){    if(nowl<=l && r<=nowr){return z[rt];}    int m = (l + r) >> 1;    bool fl = false, fr = false;    tree tl, tr, res;    if (nowl <= m){        if(m

GSS6

给出一个由 \(N\) 个整数组成的序列 \(A\)，你需要应用 \(M\) 个操作：

  • \(I\) \(p\) \(x\) 在 \(p\) 处插入插入一个元素 \(x\)
  • \(D\) \(p\) 删除 \(p\) 处的一个元素
  • \(R\) \(p\) \(x\) 修改 \(p\) 处元素的值为 \(x\)
  • \(Q\) \(l\) \(r\) 查询一个区间 \([l, r]\) 的最大子段和

思路

平衡树呗，记得push up一下刚更新的节点就好啦。

此处给出两个版本：

  • Splay版

  • FHQ Treap版

请自行选择食用QwQ

code1: (Splay)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 200010#define inf 2147483647#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0') {if (ch == '-') f = -f; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }    return x * f;}inline void write(int x){    if (x < 0) putchar('-'), x = -x;    if (x > 9) write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...vector
        
          ljt;struct tree{    int ch[2], sze, fa;    ll w, sum, lsum, rsum, msum;    tree(int s, int f, int v, int su, int l, int r, int m)        : sze(s), fa(f), w(v), sum(su), lsum(l), rsum(r), msum(m) { ch[0] = ch[1] = 0; }    tree() : tree(0, 0, 0, 0, 0, 0, 0) {}};int n, m, tot, a[mn];tree z[mn];inline int newnode(int v = 0){    int rt;    if (ljt.empty())        rt = ++tot;    else        rt = ljt.back(), ljt.pop_back();    z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = 0;    z[rt].sze = 1;    z[rt].w = z[rt].sum = v;    z[rt].lsum = z[rt].rsum = z[rt].msum = max(v, 0);    return rt;}inline void deletenode(int rt){    z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = z[rt].w = z[rt].sum = z[rt].msum = z[rt].lsum = z[rt].rsum = 0;    z[rt].sze = 1;    ljt.push_back(rt);}inline void update(int rt){    z[rt].sum = z[rt].w, z[rt].sze = 1;    if (z[rt].ch[0])        z[rt].sum += z[z[rt].ch[0]].sum, z[rt].sze += z[z[rt].ch[0]].sze;    if (z[rt].ch[1])        z[rt].sum += z[z[rt].ch[1]].sum, z[rt].sze += z[z[rt].ch[1]].sze;    if (z[rt].ch[0] && z[rt].ch[1]) {        z[rt].lsum = max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].w + z[z[rt].ch[1]].lsum);        z[rt].rsum = max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].w + z[z[rt].ch[0]].rsum);        z[rt].msum = max({z[z[rt].ch[0]].msum, z[z[rt].ch[1]].msum, z[z[rt].ch[0]].rsum + z[z[rt].ch[1]].lsum + z[rt].w});    } else if (z[rt].ch[0]) {        z[rt].lsum = max({z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].w, 0ll});        z[rt].rsum = max(z[z[rt].ch[0]].rsum + z[rt].w, 0ll);        z[rt].msum = max(z[z[rt].ch[0]].msum, z[z[rt].ch[0]].rsum + z[rt].w);    } else if (z[rt].ch[1]) {        z[rt].lsum = max(z[z[rt].ch[1]].lsum + z[rt].w, 0ll);        z[rt].rsum = max({z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].w, 0ll});        z[rt].msum = max(z[z[rt].ch[1]].msum, z[z[rt].ch[1]].lsum + z[rt].w);    } else {        z[rt].lsum = z[rt].rsum = max(z[rt].w, 0ll);        z[rt].msum = z[rt].w;    }}inline int iden(int rt) {    return z[z[rt].fa].ch[0] == rt ? 0 : 1;}inline void connect(int x, int y, int son) {    z[x].fa = y;    z[y].ch[son] = x;}inline void rotate(int x) {    int y = z[x].fa;    int moot = z[y].fa;    int yson = iden(x);    int mootson = iden(y);    int B = z[x].ch[yson ^ 1];    connect(B, y, yson), connect(y, x, yson ^ 1), connect(x, moot, mootson);    update(y), update(x);}inline void splay(int x, int &k) {    if (x == k)        return;    int p = z[k].fa;    while (z[x].fa != p) {        int y = z[x].fa;        if (z[y].fa != p)            rotate(iden(y) ^ iden(x) ? x : y);        rotate(x);    }    k = x;}inline int findkth(int rt, int k) {    while (1119) {        if (z[rt].ch[0] && k <= z[z[rt].ch[0]].sze)            rt = z[rt].ch[0];        else {            if (z[rt].ch[0])                k -= z[z[rt].ch[0]].sze;            if (!--k)                return rt;            rt = z[rt].ch[1];        }    }}inline void insert(int &rt, int p, int v) {    int x = findkth(rt, p);    splay(x, rt);    int y = findkth(rt, p + 1);    int ooo = z[rt].ch[1];    splay(y, ooo);    z[y].ch[0] = newnode(v);    z[z[y].ch[0]].fa = y;    update(z[y].ch[0]), update(y), update(x);}inline void erase(int &rt, int p) {    int y = findkth(rt, p);    splay(y, rt);    int x = findkth(rt, p + 1);    int ooo = z[rt].ch[1];    splay(x, ooo);    int oo = z[x].ch[1];    z[oo].fa = y;    z[y].ch[1] = oo;    deletenode(x);    update(y);}inline int getRange(int &rt, int l, int r) {    int x = findkth(rt, l);    splay(x, rt);    int y = findkth(rt, r + 2);    int ooo = z[rt].ch[1];    splay(y, ooo);    return z[y].ch[0];}inline void modify(int &rt, int p, ll v) {    int x = findkth(rt, p + 1);    splay(x, rt);    z[x].w = v;    update(x);}inline ll query(int &rt, int l, int r) {    int x = getRange(rt, l, r);    return z[x].msum;}inline void build(int rt, int l, int r) {    int m = (l + r) >> 1;    z[rt].w = a[m];    if (l <= m - 1) {        z[rt].ch[0] = newnode();        z[z[rt].ch[0]].fa = rt;        build(z[rt].ch[0], l, m - 1);    }    if (m + 1 <= r) {        z[rt].ch[1] = newnode();        z[z[rt].ch[1]].fa = rt;        build(z[rt].ch[1], m + 1, r);    }    update(rt);}int main(){    n = read();    go(i, 1, n, 1) a[i] = read();    int rot = ++tot;    build(rot, 0, n + 1);    m = read();    go(i, 1, m, 1)    {        char s;        cin >> s;        if (s == 'I') {            int p = read(), v = read();            insert(rot, p, v);        } else if (s == 'D') {            int p = read();            erase(rot, p);        } else if (s == 'R') {            int p = read(), x = read();            modify(rot, p, x);        } else {            int x = read(), y = read();            printf("%lld\n", query(rot, x, y));        }    }    return 0;}

code2: (FHQ Treap)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define go(i, j, n, k) for(int i = j; i <= n; i += k)#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)#define mn 400010#define inf 1 << 30#define ll long longinline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f;}struct tree{ int pri, ch[2], sze; ll x, sum, lsum, rsum, msum;} z[mn];inline void update(int rt){ z[rt].sum = z[rt].x, z[rt].sze = 1; if (z[rt].ch[0]) z[rt].sum += z[z[rt].ch[0]].sum, z[rt].sze += z[z[rt].ch[0]].sze; if (z[rt].ch[1]) z[rt].sum += z[z[rt].ch[1]].sum, z[rt].sze += z[z[rt].ch[1]].sze; if (z[rt].ch[0] && z[rt].ch[1]) { z[rt].lsum = max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x + z[z[rt].ch[1]].lsum); z[rt].rsum = max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x + z[z[rt].ch[0]].rsum); z[rt].msum = max(max(z[z[rt].ch[0]].msum, z[z[rt].ch[1]].msum), z[z[rt].ch[0]].rsum + z[z[rt].ch[1]].lsum + z[rt].x); } else if (z[rt].ch[0]) { z[rt].lsum = max(max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x), 0ll); z[rt].rsum = max(z[z[rt].ch[0]].rsum + z[rt].x, 0ll); z[rt].msum = max(z[z[rt].ch[0]].msum, z[z[rt].ch[0]].rsum + z[rt].x); } else if (z[rt].ch[1]) { z[rt].lsum = max(z[z[rt].ch[1]].lsum + z[rt].x, 0ll); z[rt].rsum = max(max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x), 0ll); z[rt].msum = max(z[z[rt].ch[1]].msum, z[z[rt].ch[1]].lsum + z[rt].x); } else { z[rt].lsum = z[rt].rsum = max(z[rt].x, 0ll); z[rt].msum = z[rt].x; }}int cnt;inline int newnode(int v = 0) { z[++cnt].x = z[cnt].msum = z[cnt].sum = v; z[cnt].lsum = z[cnt].rsum = max(v, 0); z[cnt].sze = 1; z[cnt].pri = rand(); return cnt;}inline int merge(int x, int y) { if(!x || !y) return x + y; if(z[x].pri < z[y].pri) { z[x].ch[1] = merge(z[x].ch[1], y); update(x); return x; } else { z[y].ch[0] = merge(x, z[y].ch[0]); update(y); return y; }}inline void split(int rt, int k, int &x, int &y) { if(!rt) x = y = 0; else { if(k <= z[z[rt].ch[0]].sze) { y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]); } else { x = rt, split(z[rt].ch[1], k - z[z[rt].ch[0]].sze - 1, z[rt].ch[1], y); } update(rt); }}int n, m, xx, yy, zz, rot;inline void debug() { go(rt, 1, cnt, 1) { printf("%d: pri:%d, sze:%d, ch[0]:%d, ch[1]:%d, x:%d\n", rt, z[rt].pri, z[rt].sze, z[rt].ch[0], z[rt].ch[1], z[rt].x); } printf("\n");}int main() { srand((unsigned)time(NULL)); n = read(); go(i, 1, n, 1) { int x = read(); split(rot, i, xx, yy); rot = merge(merge(xx, newnode(x)), yy); } m = read(); go(i, 1, m, 1) { char s; cin >> s; int x = read(), v; if(s == 'I') { v = read(); split(rot, x - 1, xx, yy); rot = merge(merge(xx, newnode(v)), yy); } else if(s == 'D') { split(rot, x, xx, zz); split(xx, x - 1, xx, yy); yy = merge(z[yy].ch[0], z[yy].ch[1]); rot = merge(merge(xx, yy), zz); } else if(s == 'R') { v = read(); split(rot, x, xx, zz); split(xx, x - 1, xx, yy); z[yy].x = v; z[yy].sum = z[yy].msum = v; z[yy].lsum = z[yy].rsum = max(v, 0); rot = merge(merge(xx, yy), zz); } else if(s == 'Q') { v = read(); split(rot, v, xx, zz); split(xx, x - 1, xx, yy); printf("%lld\n", z[yy].msum); rot = merge(merge(xx, yy), zz); }// debug(); } return 0;}

GSS7

给定一棵树，有$ N (N ≤ 100000) $个节点，每一个节点都有一个权值 \(x[i] (<= 10000)\)

你需要执行 \(Q (Q ≤ 100000)\) 次操作：

  • \(1\) \(a\) \(b\) 查询 \((a,b)\) 这条链上的最大子段和，可以为空（即输出\(0\)）
  • \(2\) \(a\) \(b\) \(c\) 将 \((a,b)\) 这条链上的所有点权变为 \(c (|c| <= 10000)\)

思路

树链剖分套线段树维护区间最大子段和，基本没啥思路，直接套。不过代码细节较多。代码过长，引起极度不适。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 100020#define inf 2147483647#define ll long long#define root 1, n, 1#define lson l, m, rt << 1#define rson m + 1, r, rt << 1 | 1#define bson l, r, rtinline int read(){    int f = 1, x = 0;char ch = getchar();    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}inline void write(int x){    if (x < 0)putchar('-'),x = -x;    if (x > 9)write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...int n, m, r;struct tree{    int sum, lsum, rsum, msum;    tree() { sum = lsum = rsum = msum = 0; }};int dep[mn], sze[mn], son[mn], fa[mn], id[mn], top[mn], b[mn];int cnt;// Array -------------------------------------------------------------------struct SegmentTree{    tree z[mn << 2];    int col[mn << 2];    int cd[mn << 2];    inline void update(int rt){        z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;        z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1 | 1].lsum + z[rt << 1].sum);        z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1].rsum + z[rt << 1 | 1].sum);        z[rt].msum = max({z[rt << 1].msum, z[rt << 1 | 1].msum, z[rt << 1].rsum + z[rt << 1 | 1].lsum});    }    inline tree operation(tree a,tree b){        tree res;        res.sum = a.sum + b.sum;        res.lsum = max(a.lsum, a.sum + b.lsum);        res.rsum = max(b.rsum, b.sum + a.rsum);        res.msum = max({a.msum, b.msum, a.rsum + b.lsum});        return res;    }    inline void push_col(int l,int r,int rt){        if(cd[rt]) {            int m = (l + r) >> 1;            cd[rt << 1] = cd[rt << 1 | 1] = 1;            col[rt << 1] = col[rt << 1 | 1] = col[rt];            z[rt << 1].sum = (m - l + 1) * col[rt];            z[rt << 1 | 1].sum = (r - m) * col[rt];            z[rt << 1].lsum = z[rt << 1].rsum = z[rt << 1].msum = max(z[rt << 1].sum, 0);            z[rt << 1 | 1].lsum = z[rt << 1 | 1].rsum = z[rt << 1 | 1].msum = max(z[rt << 1 | 1].sum, 0);            cd[rt] = 0;        }    }    inline void build(int l,int r,int rt){        if(l==r){            z[rt].sum = b[l];            z[rt].lsum = z[rt].rsum = z[rt].msum = max(z[rt].sum, 0);            return;        }        int m = (l + r) >> 1;        build(lson);        build(rson);        update(rt);    }    inline void modify(int l,int r,int rt,int nowl,int nowr,int v){        if(nowl<=l && r<=nowr){            col[rt] = v;            cd[rt] = 1;            z[rt].sum = (r - l + 1) * v;            z[rt].lsum = z[rt].rsum = z[rt].msum = max(z[rt].sum, 0);            return;        }        int m = (l + r) >> 1;        push_col(bson);        if(nowl<=m)            modify(lson, nowl, nowr, v);        if(m
         
          > 1; push_col(bson); if(nowl<=m){ if(m
          
            dep[y]) swap(x, y); tr.modify(root, id[x], id[y], v);}*/inline void modifyTree(int x,int y,int v){ while(top[x] != top[y]){ if(dep[top[x]] > dep[top[y]]){ tr.modify(root, id[top[x]], id[x], v); x = fa[top[x]]; }else{ tr.modify(root, id[top[y]], id[y], v); y = fa[top[y]]; } } if(dep[x] > dep[y]) tr.modify(root, id[y], id[x], v); else tr.modify(root, id[x], id[y], v);}inline tree queryTree(int x,int y){ tree lt, rt; while(top[x] != top[y]){ if(dep[top[x]] > dep[top[y]]){ tree get = tr.query(root, id[top[x]], id[x]); lt.msum = max({lt.msum, get.msum, lt.lsum + get.rsum}); lt.lsum = max(lt.lsum + get.sum, get.lsum); lt.rsum = max(lt.rsum, get.rsum + lt.sum); lt.sum += get.sum; x = fa[top[x]]; }else{ tree get = tr.query(root, id[top[y]], id[y]); rt.msum = max({rt.msum, get.msum, rt.lsum + get.rsum}); rt.lsum = max(rt.lsum + get.sum, get.lsum); rt.rsum = max(rt.rsum, rt.sum + get.rsum); rt.sum += get.sum; y = fa[top[y]]; } //cout << "lalala\n"; } //printf("%d %d %d %d\n%d %d %d %d\n", lt.lsum, lt.rsum, lt.sum, lt.msum, rt.lsum, rt.rsum, rt.sum, rt.msum); if(dep[x] < dep[y]){ tree get = tr.query(root, id[x], id[y]); rt.msum = max({rt.msum, get.msum, rt.lsum + get.rsum}); rt.lsum = max(get.lsum, get.sum + rt.lsum); rt.rsum = max(rt.rsum, rt.sum + get.rsum); rt.sum += get.sum; }else{ tree get = tr.query(root, id[y], id[x]); lt.msum = max({lt.msum, get.msum, lt.lsum + get.rsum}); lt.lsum = max(get.lsum, get.sum + lt.lsum); lt.rsum = max(lt.rsum, lt.sum + get.rsum); lt.sum += get.sum; } //cout << "lalala\n"; tree res; res.sum = lt.sum + rt.sum; res.lsum = max(lt.lsum, lt.sum + rt.rsum); res.rsum = max(rt.lsum, rt.sum + lt.rsum); res.msum = max({lt.msum, rt.msum, lt.lsum + rt.lsum}); return res;}// Modify and Query ------------------------------------------------------int main(){ n = read(); r = 1; go(i, 1, n, 1) w[i] = read(); go(i, 1, n - 1, 1){ int x = read(), y = read(); add(x, y), add(y, x); } dfs1(r, 0, 1); dfs2(r, r); tr.build(root); m = read(); go(i, 1, m, 1){ int s = read(), x = read(), y = read(); if(s==2){ int v = read(); modifyTree(x, y, v); }else{ cout << queryTree(x, y).msum << "\n"; //cout << "lalala\n"; } } return 0;}

GSS8

给你一个序列，\(A[0], A[1]...A[N - 1].\) \((0 \le A[i] \lt 2^{32})\)

你需要支持 Q 次操作

  • \(I\) \(pos\) \(val\) 插入一个数字在第 \(pos\) 个位置之前，\(0 \le val \lt 2^{32}\)
    , 如果\(pos=current\) \(length\)，那么你需要将这个数字放到序列末尾
  • D pos 删除第 \(pos\) 个元素
  • R pos val 将第 \(pos\) 个元素变为\(val(0 \le val \lt 2^{32})\)
  • Q l r k 询问\((\sum\limits_{i=l}^{r} A[i] * (i - l + 1) ^ k) \mod 2^{32}\)，保证\(0 \le k \le 10\)

思路

对于每一个 k 都维护一个答案。

如果 k = 0, 就是区间和，如果 k = 1，我们可以用这样的式子写：

z[rt].ans[1] = z[z[rt].ch[0]].ans[1] + z[z[rt].ch[1]].ans[1] + (z[z[rt].ch[1]].sum * z[z[rt].ch[0]].sze)

但如果我们考虑 k > 1，我们仍考虑左右合并，但不是左边不动的，我们把表达式化简一下。（以下计算过程参考 hzk_cpp 巨佬的 计算过程）

\(A[i](i - l + 1)^k\)

= \(A[i]((mid - l + 1) + (i - mid))^k\)

另 \(x = i - l + 1\)，实际就是左区间的长度，设 $ rs.ans[j] $ 作为 \([min + 1, r]\) 时 \(k = j\) 的答案。

= \(A[i](x + i - mid)^k\)

由二项式定理得

= \(A[i]\sum_{j=0}^kC_k^jx^{k-j}(i - mid)^j\)

我们右边所有的值加起来，得：

= \(\sum_{i=mid+1}^rA[i]\sum_{j=0}^kC_k^jx^{k-j}(i - mid)^j\)

= \(\sum_{i=mid+1}^r\sum_{j=0}^kA[i]C_k^jx^{k-j}(i - mid)^j\)

= \(\sum_{j=0}^kC_k^jx^{k-j}rs.ans[j]\)

这个式子直接可以暴力在update函数中直接更新，毕竟 \(k <= 10\)，不伤身体。

目前只有Splay版，FHQ Treap版正在调。

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define go(i, j, n, k) for (int i = j; i <= n; i += k)#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)#define mn 200010#define inf 2147483647#define ll unsigned intinline ll read(){    ll x = 0; char ch = getchar();     while (ch > '9' || ch < '0') { ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }    return x;}inline void write(int x){    if (x < 0) putchar('-'), x = -x;    if (x > 9) write(x / 10);    putchar(x % 10 + '0');}//This is AC head above...vector
         
           ljt;struct tree{ int ch[2], sze, fa; ll w, ans[11]; tree(int s, int f, int v) : sze(s), fa(f), w(v) { ch[0] = ch[1] = 0; go(i, 0, 10, 1) ans[i] = 0; } tree() : tree(0, 0, 0) {}};int n, m, tot;ll a[mn];tree z[mn];ll po[mn], C[11][11];inline int newnode(int v = 0){ int rt; if (ljt.empty()) rt = ++tot; else rt = ljt.back(), ljt.pop_back(); z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = 0; z[rt].sze = 1; z[rt].w = v; return rt;}inline void deletenode(int rt){ z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = z[rt].w = 0; go(i, 0, 10, 1) z[rt].ans[i] = 0; z[rt].sze = 1; ljt.push_back(rt);}inline void update(int rt) { z[rt].sze = 1; if(z[rt].ch[0]) z[rt].sze += z[z[rt].ch[0]].sze; if(z[rt].ch[1]) z[rt].sze += z[z[rt].ch[1]].sze; po[0] = 1ll; go(i, 1, 10, 1) po[i] = po[i - 1] * (z[z[rt].ch[0]].sze + 1); go(i, 0, 10, 1) { z[rt].ans[i] = z[z[rt].ch[0]].ans[i] + z[rt].w * po[i]; go(j, 0, i, 1) z[rt].ans[i] = z[rt].ans[i] + z[z[rt].ch[1]].ans[j] * po[i - j] * C[i][j]; }}inline int iden(int rt) { return z[z[rt].fa].ch[0] == rt ? 0 : 1;}inline void connect(int x, int y, int son) { z[x].fa = y; z[y].ch[son] = x;}inline void rotate(int x) { int y = z[x].fa; int moot = z[y].fa; int yson = iden(x); int mootson = iden(y); int B = z[x].ch[yson ^ 1]; connect(B, y, yson), connect(y, x, yson ^ 1), connect(x, moot, mootson); update(y), update(x);}inline void splay(int x, int &k) { if (x == k) return; int p = z[k].fa; while (z[x].fa != p) { int y = z[x].fa; if (z[y].fa != p) rotate(iden(y) ^ iden(x) ? x : y); rotate(x); } k = x;}inline int findkth(int rt, int k) { while (1119) { if (z[rt].ch[0] && k <= z[z[rt].ch[0]].sze) rt = z[rt].ch[0]; else { if (z[rt].ch[0]) k -= z[z[rt].ch[0]].sze; if (!--k) return rt; rt = z[rt].ch[1]; } }}inline void insert(int &rt, int p, int v) { int x = findkth(rt, p); splay(x, rt); int y = findkth(rt, p + 1); int ooo = z[rt].ch[1]; splay(y, ooo); z[y].ch[0] = newnode(v); z[z[y].ch[0]].fa = y; update(z[y].ch[0]), update(y), update(x);}inline void erase(int &rt, int p) { int y = findkth(rt, p); splay(y, rt); int x = findkth(rt, p + 1); int ooo = z[rt].ch[1]; splay(x, ooo); int oo = z[x].ch[1]; z[oo].fa = y; z[y].ch[1] = oo; deletenode(x); update(y);}inline int getRange(int &rt, int l, int r) { int x = findkth(rt, l); splay(x, rt); int y = findkth(rt, r + 2); int ooo = z[rt].ch[1]; splay(y, ooo); return z[y].ch[0];}inline void modify(int &rt, int p, ll v) { int x = findkth(rt, p + 1); splay(x, rt); z[x].w = v; update(x);}inline ll query(int &rt, int l, int r, int k) { int x = getRange(rt, l, r); return z[x].ans[k];}inline void build(int rt, int l, int r) { int m = (l + r) >> 1; z[rt].w = a[m]; if (l <= m - 1) { z[rt].ch[0] = newnode(); z[z[rt].ch[0]].fa = rt; build(z[rt].ch[0], l, m - 1); } if (m + 1 <= r) { z[rt].ch[1] = newnode(); z[z[rt].ch[1]].fa = rt; build(z[rt].ch[1], m + 1, r); } update(rt);}inline void init() { go(i, 0, 10, 1) C[i][0] = C[i][i] = 1; go(i, 1, 10, 1) go(j, 1, i, 1) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];// go(i, 0, 10, 1) // go(j, 0, 10, 1) // printf("%5d%c", C[i][j], (j == 10) ? '\n' : ' ');}int main(){ init(); n = read(); go(i, 1, n, 1) a[i] = read(); int rot = ++tot; build(rot, 0, n + 1); m = read(); go(i, 1, m, 1) { char s; cin >> s; if (s == 'I') { int p = read() + 1, v = read(); insert(rot, p, v); } else if (s == 'D') { int p = read() + 1; erase(rot, p); } else if (s == 'R') { int p = read() + 1, x = read(); modify(rot, p, x); } else { int x = read() + 1, y = read() + 1, z = read(); printf("%lld\n", query(rot, x, y, z)); } } return 0;}

所有系列题目完成于 2019 / 3 / 25 23 : 02 : 29

转载于:https://www.cnblogs.com/yizimi/p/10597818.html

你可能感兴趣的文章
【动态规划】skiing
查看>>
java定时器的使用（Timer）
查看>>
ef codefirst VS里修改数据表结构后更新到数据库
查看>>
boost 同步定时器
查看>>
[ROS] Chinese MOOC || Chapter-4.4 Action
查看>>
简单的数据库操作
查看>>
解决php -v查看到版本与phpinfo()版本不一致问题
查看>>
iOS-解决iOS8及以上设置applicationIconBadgeNumber报错的问题
查看>>
亡灵序曲-The Dawn
查看>>
Redmine
查看>>
帧的最小长度 CSMA/CD
查看>>
xib文件加载后设置frame无效问题
查看>>
编程算法 - 左旋转字符串 代码(C)
查看>>
IOS解析XML
查看>>
Python3多线程爬取meizitu的图片
查看>>
树状数组及其他特别简单的扩展
查看>>
zookeeper适用场景：分布式锁实现
查看>>
110104_LC-Display(液晶显示屏)
查看>>
httpd_Vhosts文件的配置
查看>>
php学习笔记
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-24 12:36:27   当前IP: 3.149.214.223   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我