任务查询系统

题意：区间修改（修改区间每个位置某个数的数量，注意每个位置有多个数）+单点查询前K小的权值和+强制在线

思路：

  1. 由于主席树运用了前缀和思想，每个位置保存了所有权值的前缀和；因此若此题的区间修改利用差分思想，则主席树的每个位置恰好就维护的是自身位置（差分与前缀和相互抵消了），也就是不必手动求前缀和了。
  2. 这样我们就只需要离散化一下，然后利用差分思想处理所有的修改
  3. 而主席树部分跟普通主席树不同的是，主席树的每个位置并不是维护前缀和了（这样反而使代码更简单了），而是维护的自身位置的权值线段树（相当于n棵普通的权值线段树）

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-7;

int m, n, nn, tot;
int T[maxn<<6], sz[maxn<<6], L[maxn<<6], R[maxn<<6];
int s[maxn], e[maxn], p[maxn], b[maxn];
ll sum[maxn<<6];
vector<pr> q[maxn];

void update(int x, int f, int l, int r, int pre, int &now) { //x表示插入的权值，f取-1表示删去，取0表示建树即可，取1表示插入
    now=++tot;
    L[now]=L[pre], R[now]=R[pre], sz[now]=sz[pre]+f, sum[now]=sum[pre]+b[x]*f;
    if(l==r) return;
    int m=(l+r)/2;
    if(x<=m) update(x,f,l,m,L[pre],L[now]);
    else update(x,f,m+1,r,R[pre],R[now]);
}

ll qksum(int k, int x, int l, int r) {
    if(l==r) return min(k,sz[x])*1ll*b[l];
    int s=sz[L[x]]; //这里不需要处理前缀和了
    int m=(l+r)/2;
    if(s>=k) return qksum(k,L[x],l,m);
    else return sum[L[x]]+qksum(k-s,R[x],m+1,r);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    m=read(), n=read();
    for(int i=1; i<=m; ++i) s[i]=read(), e[i]=read(), p[i]=b[i]=read();
    sort(b+1,b+1+m); nn=unique(b+1,b+1+m)-b-1;
    for(int i=1; i<=m; ++i) {
        int d=lower_bound(b+1,b+1+nn,p[i])-b;
        q[s[i]].push_back(pr(d,1));
        if(e[i]<n) q[e[i]+1].push_back(pr(d,-1)); //这里注意n+1就不用处理了，因为只有n棵权值线段树
    }
    for(int i=1; i<=n; ++i) {
        update(1,0,1,nn,T[i-1],T[i]);
        for(int j=0; j<q[i].size(); ++j)
            update(q[i][j].first,q[i][j].second,1,nn,T[i],T[i]);
    }
    ll pre=1;
    for(int i=1; i<=n; ++i) {
        int x=read(), A=read(), B=read(), C=read();
        int k=(pre*A+B)%C+1;
        printf("%lld\n", pre=qksum(k,T[x],1,nn));
    }
}