题目大意：在[s,e]（闭区间）上加入一个数字k（就相当于在s时刻放入，e+1时刻取出）。支持询问在t时刻时的第k大数。
想一想就可以知道主席树能水过这道题。
/************************************************************** Problem: 3932 User: geng4512 Language: C++ Result: Accepted Time:3808 ms Memory:192900 kb****************************************************************/#include#include #include #define MAXN 100005#define LL long longusing namespace std;struct node { int lc, rc, cnt; long long sum;} t[MAXN*80];vector L[MAXN], R[MAXN];int n, m, rt[MAXN], cnt, tag, mark[MAXN*80];char c;inline void GET(int &n) { n = 0; do c = getchar(); while('0' > c || c > '9'); do n = n*10+c-'0', c = getchar(); while('0' <= c && c <= '9');}inline void Build(int &rt, int x) { t[rt = ++ cnt] = t[x]; mark[rt] = tag;}void Insert(int &rt, int p, int v, int l, int r, char f) { if(mark[p] != tag) Build(rt, p); t[rt].cnt += f; t[rt].sum += v*f; if(l >= r) return; int mid = (l + r) >> 1; if(v <= mid) Insert(t[rt].lc, t[p].lc, v, l, mid, f); else Insert(t[rt].rc, t[p].rc, v, mid+1, r, f);}long long Query(int x, int l, int r, int k) { if(l >= r) return 1LL * k * l; int mid = (l + r) >> 1; if(t[t[x].lc].cnt >= k) return Query(t[x].lc, l, mid, k); return Query(t[x].rc, mid+1, r, k - t[t[x].lc].cnt) + t[t[x].lc].sum;}int main() { int s, e, v, x, mn=MAXN, mx=-1; long long p = 1; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++ i) { GET(s); GET(e); GET(v); L[s].push_back(v); R[e].push_back(v); mn = min(mn, s); mx = max(mx, e); } for(int i = mn; i <= mx; ++ i) { Build(rt[i], rt[i-1]); ++tag; for(int j = 0; j < (int)L[i].size(); ++ j) Insert(rt[i], rt[i], L[i][j], 1, 1e7, 1); for(int j = 0; j < (int) R[i-1].size(); ++ j) Insert(rt[i], rt[i], R[i-1][j], 1, 1e7, -1); } for(int i = 1; i <= m; ++ i) { GET(x); GET(s); GET(e); GET(v); v = 1 + (p*s+e)%v; if(v >= t[rt[x]].cnt) p = t[rt[x]].sum; else p = Query(rt[x], 1, 1e7, v); printf("%lld\n", p); } return 0;}