吐槽:劳资终于过了…留念一下…
题目大意
给定一个长度为 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(); } } }
zjq
您的码力好强啊Orz,您码所有题都好强啊QAQ
求加个好友QAQ,蒟蒻QQ5086401