[考试题目]哲学家 数据结构

吐槽:劳资终于过了…留念一下…

题目大意

给定一个长度为 n 的序列，m 次操作，操作有两种：一种是将其一个区间升序/降序排序，一种是询问区间元素积的十进制下最高位是什么数。
N,M<=200000.

解题报告

这题复杂度很玄学…大致思路就是用一个数据结构A维护所有有序区间,然后每个有序区间再搞一个数据结构B维护权值,查询直接用数据结构A先查询,两端的区间搞出来然后进入数据结构B再查询。

修改操作就非常地玄学了…用数据结构B暴力合并,感觉代码一阵危险…但是能过?

然后…本人非常不幸地选取了使用分裂式Treap维护权值,Splay维护区间…

Treap合并操作大约长这样(玄):

    int merge (int a, int b) {
        if(!a || !b) return a|b;
        if(d[a].prio < d[b].prio) swap(a, b);
        pair<int, int> bs = splitv(b, d[a].val); // 按照节点a的权值分裂子树b
        d[a].ch[0] = merge(d[a].ch[0], bs.first);
        d[a].ch[1] = merge(d[a].ch[1], bs.second);
        updata(a);
        return a;
    }

看着就觉得很危险…但是我还是信仰了一波,码了12kb代码,然后过了…速度快过标程,内存开销奇小…然而代码长度被虐杀

反正我是这么过了,纪念一下。

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <stack>
#include <cmath>
using namespace std;
const double EPS = 1e-6;
const int MAXD = 500000;
const int MAXN = 200100;

namespace Treap {
    struct Node {
        int ch[2], prio, sz;
        double val, prod;
    } d[MAXD];
    int dtot;
    int newNode (int val) {
        dtot++;
        d[dtot].prod = d[dtot].val = log10(val);
        d[dtot].sz = 1;
        d[dtot].prio = rand()*rand();
        return dtot;
    }
    void updata (int u) {
        d[u].prod = d[u].val;
        d[u].sz = 1+d[d[u].ch[0]].sz+d[d[u].ch[1]].sz;
        d[u].prod += d[d[u].ch[0]].prod;
        d[u].prod += d[d[u].ch[1]].prod;
    }

    pair<int, int> split (int u, int sz, bool flg) {
        if(!u) return make_pair(0, 0);
        if(!sz) return make_pair(0, u);
        if(d[u].sz <= sz) return pair<int, int> (u, 0);
        if(d[d[u].ch[flg]].sz >= sz) {
            pair<int, int> lef = split(d[u].ch[flg], sz, flg);
            d[u].ch[flg] = lef.second;
            updata(u);
            lef.second = u;
            return lef;
        } else {
            pair<int, int> rig = split(d[u].ch[!flg], sz-d[d[u].ch[flg]].sz-1, flg);
            d[u].ch[!flg] = rig.first;
            updata(u);
            rig.first = u;
            return rig;
        }
    }

    double query (int u, int sz, bool flg) {
        double ret = 0.0;
        while(u) {
            if(d[d[u].ch[flg]].sz >= sz) u = d[u].ch[flg];
            else {
                sz -= d[d[u].ch[flg]].sz+1;
                ret += d[d[u].ch[flg]].prod+d[u].val;
                u = d[u].ch[!flg];
            }
            if(!sz) return ret;
        }
        return ret;
    }

    pair<int, int> splitv (int u, double val) {
        if(!u) return pair<int, int> (0, 0);
        if(d[u].val < val) {
            pair<int, int> rig = splitv(d[u].ch[1], val);
            d[u].ch[1] = rig.first;
            updata(u);
            rig.first = u;
            return rig;
        } else {
            pair<int, int> lef = splitv(d[u].ch[0], val);
            d[u].ch[0] = lef.second;
            updata(u);
            lef.second = u;
            return lef;
        }
    }

    int merge (int a, int b) {
        if(!a || !b) return a|b;
        if(d[a].prio < d[b].prio) swap(a, b);
        pair<int, int> bs = splitv(b, d[a].val);
        d[a].ch[0] = merge(d[a].ch[0], bs.first);
        d[a].ch[1] = merge(d[a].ch[1], bs.second);
        updata(a);
        return a;
    }
    void debug () {
        for(int i = 1; i<=dtot; i++) {
            if(d[i].ch[0] == i || d[i].ch[1] == i)
                printf("Alert! Node[%d]\n", i);
        }
    }
}
struct Interval {
    int l, r, rid;
    bool rev;
    Interval () {}
    Interval(int a, int b, int c, bool d = false):l(a), r(b), rid(c), rev(d){}
    bool operator < (Interval b) const {return l < b.l;}
    bool operator > (Interval b) const {return l > b.l;}
    bool operator == (Interval b) const {return l==b.l && r==b.r;}
    double getValue () {return Treap :: d[rid].prod;}
};
namespace Splay {
    struct Node {
        int ch[2], fa;
        Interval val;
        double prod;
    } d[MAXD];
    int dtot = 0;
    stack<int> memo;
    int newNode (Interval val) {
        int u;
        if(!memo.empty()) u = memo.top(), memo.pop();
        else u = ++dtot;
        memset(d+u, 0, sizeof d[0]);
        d[u].val = val;
        d[u].prod = Treap :: d[val.rid].prod;
        return u;
    }
    void updata (int u) {
        d[u].prod = Treap::d[d[u].val.rid].prod;
        d[u].prod += d[d[u].ch[0]].prod;
        d[u].prod += d[d[u].ch[1]].prod;
    }
    void rotate (int x) {
        int y = d[x].fa;
        bool f = (d[y].ch[1]==x);
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1]==y] = x;
        updata(y), updata(x);
    }
    int root;
    void splay (int x, int g = 0) {
        updata(x);
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1]==y) == (d[y].ch[1]==x))
                    rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        if(!g) root = x;
    }
    int locate (Interval inv) {
        int u = root, l = 0;
        while(u) {
            l = u;
            if(d[u].val == inv) return u;
            if(d[u].val < inv) u = d[u].ch[1];
            else u = d[u].ch[0];
        }
        return l;
    }
    void insert (Interval val) {
        if(root == 0) {root = newNode(val); return ;}
        int pos = locate(val);
        splay(d[d[pos].ch[d[pos].val < val] = newNode(val)].fa = pos, 0);
    }
    void release (int u) {
        if(!u) return ;
        memo.push(u);
        release(d[u].ch[0]);
        release(d[u].ch[1]);
    }
    void eraseTree (int u) {
        d[d[u].fa].ch[d[d[u].fa].ch[1]==u] = 0;
        if(!d[u].fa) root = 0;
        else splay(d[u].fa, 0);
        d[u].fa = 0;
        release(u);
    }

    int getNext (int u, bool flg) {
        splay(u, 0);
        u = d[u].ch[flg];
        while(d[u].ch[!flg]) u = d[u].ch[!flg];
        return u;
    }
    int * tail;
    void printInvId (int u) {
        if(!u) return ;
        *(++tail) = d[u].val.rid;
        printInvId(d[u].ch[0]);
        printInvId(d[u].ch[1]);
    }
    int getInterval (int ul, int ur) {
        int l = getNext(ul, false), r = getNext(ur, true);
        splay(l, 0);
        splay(r, l);
        return d[r].ch[0];
    }
    void debug (int u) {
        if(!u) return ;
        debug(d[u].ch[0]);
        *(++tail) = u;
        debug(d[u].ch[1]);
    }
}

int A[MAXN];
int temp[MAXN];
int merge (int l, int r) {
    if(l == r) return temp[l];
    int mid = (l+r)>>1;
    int x = merge(l, mid), y = merge(mid+1, r);
    return Treap :: merge(x, y);
}
bool isIn (Interval a, Interval b) {
    return a.l <= b.l && a.r >= b.r;
}
void handleModification (int l, int r, bool flg) {
    Interval lefi(l, l, 0), rigi(r, r, 0);
    int ul = Splay :: locate(lefi), ur = Splay :: locate(rigi), ll = 0, rr = 0;
    while(Splay::d[ul].val.l < l) ll = ul, ul = Splay :: getNext(ul, true);
    while(Splay::d[ur].val.r > r) rr = ur, ur = Splay :: getNext(ur, false);
    if(!ll) ll = Splay :: getNext(ul, false);
    if(!rr) rr = Splay :: getNext(ur, true);
    Interval tinv(l, r, 0);
    if(isIn(Splay::d[ll].val, tinv) || isIn(Splay::d[ul].val, tinv)) {
        if(isIn(Splay::d[ul].val, tinv)) ll = ul;
        if(Splay::d[ll].val.rev == flg) return ;
        Interval rec = Splay::d[ll].val;
        pair<int, int> pr1 = Treap :: split(Splay::d[ll].val.rid, l-Splay::d[ll].val.l, rec.rev);
        pair<int, int> pr2 = Treap :: split(pr1.second, r-l+1, rec.rev);
        int mid = pr2.first;
        Splay :: eraseTree(Splay :: getInterval(ll, ll));
        if(l > rec.l) Splay :: insert(Interval(rec.l, l-1, pr1.first, rec.rev));
        Splay :: insert(Interval(l, r, mid, flg));
        if(r < rec.r) Splay :: insert(Interval(r+1, rec.r, pr2.second, rec.rev));
        return ;
    }
    int tid = 0;
    if(Splay::d[ul].val.l <= Splay::d[ur].val.r) {
        int invid = Splay :: getInterval(ul, ur);
        Splay :: tail = temp;
        Splay :: printInvId(invid);
        tid = merge(1, Splay::tail-temp);
        Splay :: eraseTree(invid);
    }
    if(Splay::d[ll].val.r >= l) {
        bool trev = Splay::d[ll].val.rev;
        pair<int, int> pr = Treap :: split(
            Splay :: d[ll].val.rid, l-Splay::d[ll].val.l, trev);
        Splay :: eraseTree(Splay :: getInterval(ll, ll));
        Splay :: insert(Interval(Splay :: d[ll].val.l, l-1, pr.first, trev));
        tid = Treap :: merge(pr.second, tid);
    }
    if(Splay::d[rr].val.l <= r) {
        bool trev = Splay::d[rr].val.rev;
        pair<int, int> pr = Treap :: split(
            Splay :: d[rr].val.rid, r+1-Splay::d[rr].val.l, trev);
        Splay :: eraseTree(Splay :: getInterval(rr, rr));
        Splay :: insert(Interval(r+1, Splay::d[rr].val.r, pr.second, trev));
        tid = Treap :: merge(pr.first, tid);
    }
    Interval inv(l, r, tid, flg);
    Splay :: insert(inv);
}
inline int getAnswer (double val) {
    return pow(10.0, val-(int)val);
}
int handleQuery (int l, int r) {
    Interval lefi(l, l, 0), rigi(r, r, 0);
    int ul = Splay :: locate(lefi), ur = Splay :: locate(rigi), ll = 0, rr = 0;
    while(Splay::d[ul].val.l < l) ll = ul, ul = Splay :: getNext(ul, true);
    while(Splay::d[ur].val.r > r) rr = ur, ur = Splay :: getNext(ur, false);
    if(!ll) ll = Splay :: getNext(ul, false);
    if(!rr) rr = Splay :: getNext(ur, true);
    Interval tinv(l, r, 0);
    if(isIn(Splay::d[ll].val, tinv) || isIn(Splay::d[ul].val, tinv)) {
        if(isIn(Splay::d[ul].val, tinv)) ll = ul;
        return getAnswer(
        Treap :: query(Splay::d[ll].val.rid, r-Splay::d[ll].val.l+1, Splay::d[ll].val.rev) -
        Treap :: query(Splay::d[ll].val.rid, l-Splay::d[ll].val.l, Splay::d[ll].val.rev));
    }
    double ans = 0.0;
    if(Splay::d[ul].val.l <= Splay::d[ur].val.r) {
        int invid = Splay :: getInterval(ul, ur);
        ans += Splay :: d[invid].prod;
    }
    if(Splay::d[ll].val.r >= l)
        ans += Treap :: query(
            Splay :: d[ll].val.rid, Splay::d[ll].val.r-l+1, !Splay::d[ll].val.rev);
    if(Splay::d[rr].val.l <= r)
        ans += Treap :: query(
            Splay :: d[rr].val.rid, r+1-Splay::d[rr].val.l, Splay::d[rr].val.rev);
    return getAnswer(ans);
}
inline int getInt () {
    int ret = 0; bool flg = false; char ch;
    while((ch = getchar()) < '0' || ch > '9') flg ^= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
int main () {
	freopen("philosopher.in", "r", stdin);
	freopen("philosopher.out", "w", stdout);
    srand(20010627);
    int N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++)
        A[i] = getInt();
    for(int i = 1; i<=N; i++)
        Splay :: insert(Interval(i, i, Treap :: newNode(A[i])));
    Splay :: insert(Interval(0, 0, 0));
    Splay :: insert(Interval(N+1, N+1, 0));
    while(M--) {
        int typ, l, r;
        typ = getInt(), l = getInt(), r = getInt();
        if(typ == 1) handleModification(l, r, getInt()^1);
        else if(typ == 2) printf("%d\n", handleQuery(l, r));
        else {
            Splay :: tail = temp;
            Splay :: debug(Splay :: root);
            for(int * pos = temp+1; pos <= Splay :: tail; pos++)
                printf("[%d, %d]:%.2f\n",
                Splay::d[*pos].val.l, Splay::d[*pos].val.r, pow(10, Treap::d[Splay::d[*pos].val.rid].prod));
            Treap :: debug();
        }
    }
}