题目传送门(BZOJ)
>原文链接<

题解 :

考试的时候想了一个麻烦的树套树, 然鹅没有调出来.

其实非常简单, 一棵权值线段树就可以解决.

把$l, r, p$看成时间轴上的点, $l$是插入, $p$是查询, $r$是删除.

我们直接把每个布娃娃换成三个操作, 按时间排序, 在权值线段树上插入删除查询即可.

因为在某个布娃娃插入了之后, 删除之前, 我们还遇到了这个$p$,代表$l[j]\le p[i]\le r[j]$

注意, 由于都是非严格小于, 删除操作要在$r+1$上做.

生成数据的代码比写的线段树还长, 不知道出题人为啥这么丧病 ?

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int p = 19921228;const int N = 201000;const int INF = 1e8;struct Node { int p, l, r, c;}a[N];struct Quey { int pos, flg, id; Quey(int _pos = 0, int _flg = 0, int _id = 0) : pos(_pos), flg(_flg), id(_id) {} bool operator < (const Quey &A) const { return pos == A.pos ? flg < A.flg :pos < A.pos; }}q[N<<2];int t[N<<6], ls[N<<6], rs[N<<6], cnt, n, ans;int Padd, Pfirst, Pmod, Pprod, Cadd, Cfirst, Cmod, Cprod, Ladd, Lfirst, Lmod, Lprod, Radd, Rfirst, Rmod, Rprod;inline void Creat() { cin >> n >> Padd >> Pfirst >> Pmod >> Pprod >> Cadd >> Cfirst >> Cmod >> Cprod >> Ladd >> Lfirst >> Lmod >> Lprod >> Radd >> Rfirst >> Rmod >> Rprod ; a[1].p = Pfirst%Pmod; a[1].c = Cfirst%Cmod; a[1].l = Lfirst%Lmod; a[1].r = Rfirst%Rmod; for(int i = 2; i <= n; i ++ ) { a[i].p=(1ll*a[i-1].p*Pprod+Padd+i)%Pmod; a[i].c=(1ll*a[i-1].c*Cprod+Cadd+i)%Cmod; a[i].l=(1ll*a[i-1].l*Lprod+Ladd+i)%Lmod; a[i].r=(1ll*a[i-1].r*Rprod+Radd+i)%Rmod; } for(int i = 1; i <= n; i ++ ) { if(a[i].l > a[i].r) swap(a[i].l, a[i].r); q[++cnt] = Quey(a[i].l, 1, i); q[++cnt] = Quey(a[i].r+1, 2, i); q[++cnt] = Quey(a[i].p, 3, i); }}void change(int l, int r, int &p, int x, int c) { static int _; if(!p) p = ++_; t[p] += c; if(l == r) return ; int mi = (l+r) >> 1; if(x <= mi) change(l, mi, ls[p], x, c); else change(mi+1, r, rs[p], x, c);}int inq(int l, int r, int p, int k) { if(l == r) return l; int mi = (l+r) >> 1; if(k <= t[ls[p]]) return inq(l, mi, ls[p], k); else return inq(mi+1, r, rs[p], k-t[ls[p]]); }int main() { Creat(); int now = 0, root = 0; sort(q+1, q+cnt+1); for(int i = 1; i <= cnt; i ++ ) { if(q[i].flg == 1) { ++now; change(0, INF, root, a[q[i].id].c, 1); } if(q[i].flg == 2) { --now; change(0, INF, root, a[q[i].id].c, -1); } if(q[i].flg == 3) { if(now >= q[i].id) { ans += inq(0, INF, root, now-q[i].id+1); ans %= p; } } } printf("%d\n", ans);}