C58 可持久化线段树+差分 P3168 [CQOI2015] 任务查询系统 C58 可持久化线段树+差分 P3168 [CQOI2015] 任务查询系统

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

void read(int &x){ //快读
  x=0; char c=getchar();
  while(!isdigit(c))c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar();
}
typedef long long ll;
const int N=100005;
#define mid ((l+r)>>1)
int n,m,a[N],b[N],bn;
vector<int>st[N],ed[N];
int root[N],tot; //根节点,开点个数
int ls[N*50],rs[N*50],cnt[N*50]; ll sum[N*50];
// st[x]:起点为x时刻的任务, ed[x]:终点为x时刻的任务
// cnt:区间的任务个数, sum:区间的优先级之和

void change(int &u,int v,int l,int r,int p,int k){ //点修
  u=++tot; //动态开点
  ls[u]=ls[v]; rs[u]=rs[v];
  cnt[u]=cnt[v]+k; sum[u]=sum[v]+k*b[p];
  if(l==r) return;
  if(p<=mid) change(ls[u],ls[v],l,mid,p,k);
  else change(rs[u],rs[v],mid+1,r,p,k);
}
ll query(int u,int l,int r,int k){ //点查
  if(l==r) return sum[u]/cnt[u]*k;
  int s=cnt[ls[u]];
  if(k<=s) return query(ls[u],l,mid,k);
  return query(rs[u],mid+1,r,k-s)+sum[ls[u]];
}
int main(){
  read(m),read(n);
  for(int i=1,x,y; i<=m; i++){ //m个任务
    read(x);read(y);read(a[i]);b[i]=a[i];
    st[x].push_back(i); ed[y+1].push_back(i);
  }
  sort(b+1,b+1+m); //把优先级离散化
  bn=unique(b+1,b+1+m)-b-1;
  for(int i=1; i<=n; i++){ //按时刻建持久树
    root[i]=root[i-1];
    for(auto j:st[i]){ //起点为i的任务
      int p=lower_bound(b+1,b+1+bn,a[j])-b;
      change(root[i],root[i],1,bn,p,1);
    }
    for(auto j:ed[i]){ //终点为i的任务
      int p=lower_bound(b+1,b+1+bn,a[j])-b;
      change(root[i],root[i],1,bn,p,-1);
    }
  }
  ll pre=1;
  for(int i=1,x,a,b,c,k; i<=n; i++){ //n次查询
    read(x);read(a);read(b);read(c);
    k=(1ll*a*pre+b)%c+1;
    if(k>cnt[root[x]])pre=sum[root[x]];
    else pre=query(root[x],1,bn,k);
    printf("%lld\n",pre);
  }
}

C58 可持久化线段树+差分 P3168 [CQOI2015] 任务查询系统

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

void read(int &x){ //快读 x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=x10+c-'0',c=getchar(); } typedef long long ll; const int N=100005; #define mid ((l+r)>>1) int n,m,a[N],b[N],bn; vector<int>st[N],ed[N]; int root[N],tot; //根节点,开点个数 int ls[N50],rs[N50],cnt[N50]; ll sum[N*50]; // st[x]:起点为x时刻的任务, ed[x]:终点为x时刻的任务 // cnt:区间的任务个数, sum:区间的优先级之和

void change(int &u,int v,int l,int r,int p,int k){ //点修 u=++tot; //动态开点 ls[u]=ls[v]; rs[u]=rs[v]; cnt[u]=cnt[v]+k; sum[u]=sum[v]+kb[p]; if(lr) return; if(p<=mid) change(ls[u],ls[v],l,mid,p,k); else change(rs[u],rs[v],mid+1,r,p,k); } ll query(int u,int l,int r,int k){ //点查 if(lr) return sum[u]/cnt[u]k; int s=cnt[ls[u]]; if(k<=s) return query(ls[u],l,mid,k); return query(rs[u],mid+1,r,k-s)+sum[ls[u]]; } int main(){ read(m),read(n); for(int i=1,x,y; i<=m; i++){ //m个任务 read(x);read(y);read(a[i]);b[i]=a[i]; st[x].push_back(i); ed[y+1].push_back(i); } sort(b+1,b+1+m); //把优先级离散化 bn=unique(b+1,b+1+m)-b-1; for(int i=1; i<=n; i++){ //按时刻建持久树 root[i]=root[i-1]; for(auto j:st[i]){ //起点为i的任务 int p=lower_bound(b+1,b+1+bn,a[j])-b; change(root[i],root[i],1,bn,p,1); } for(auto j:ed[i]){ //终点为i的任务 int p=lower_bound(b+1,b+1+bn,a[j])-b; change(root[i],root[i],1,bn,p,-1); } } ll pre=1; for(int i=1,x,a,b,c,k; i<=n; i++){ //n次查询 read(x);read(a);read(b);read(c); k=(1llapre+b)%c+1; if(k>cnt[root[x]])pre=sum[root[x]]; else pre=query(root[x],1,bn,k); printf("%lld\n",pre); } }</pre>