bzoj3932: [CQOI2015]任务查询系统（主席树）
[CQOI2015]任务查询系统
思路
按时间顺序建权值线段树，对于每个三元组，在Si的树上Pi的位置+1，Ei+1的树上Pi的位置-1，这样对于每次询问的时间区间T[r] - T[l-1]求前k个的和就行了，需要注意的是询问的时候当l==r时这个位置的值不能全部取走，要取走相应的剩下的那k个。
代码
#include <bits/stdc++.h>
using namespace std;
#define dd(x) cout<<#x<<"="<<x<<" "
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define de(x) cout<<#x<<"="<<x<<"\n"
#define mes(p) memset(p,0,sizeof(p))
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sz(x) (int)x.size()
#define pb push_back
#define ls (rt<<1)
#define rs (ls|1)
#define all(x) x.begin(),x.end()
const int maxn=100005;
typedef long long ll;
typedef vector <int > vi;
typedef pair <int, int> pi;
int T[maxn<<7], l[maxn<<7], r[maxn<<7];
ll sum[maxn<<7];
int cnt,s[maxn<<7], n, m;
vector <ll > vv;
vector < pair < int ,ll > > v;
void upd(int pre, int &now,int L,int R,int t,ll p){
now = ++cnt;
sum[now]=sum[pre]+p;
s[now]=s[pre]+p/abs(p);
l[now]=l[pre];
r[now]=r[pre];
if(L==R) return ;
int mid= L+R>>1;
if(t<=mid )upd(l[pre],l[now],L,mid,t,p);
else upd(r[pre],r[now],mid+1,R,t,p);
}
ll qr(int now ,int k,int L,int R ){
if(L==R){
return 1ll*k*sum[now]/s[now];
}
if(s[now]==0) return 0;
int mid = L+R>>1;
if(k>s[l[now]]) return qr(r[now], k-s[l[now]],mid+1,R)+sum[l[now]];
return qr(l[now],k,L,mid);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>> n>> m;
rep(i,0,n){
int l,r;
ll p;
cin>> l >> r>> p;
v.pb({l,p});
v.pb({r+1,-p});
vv.pb(p);
}
sort(all(vv));
vv.erase(unique(all(vv)),vv.end());
int t=0, mm=sz(vv);
sort(all(v));
rep(i,1,m+1){
T[i] = T[i-1];
while(t<sz(v)&& v[t].fi<=i){
int k = lower_bound(all(vv),abs(v[t].se)) - vv.begin() + 1;
upd(T[i],T[i],1,sz(vv),k,v[t].se);
t++;
}
}
ll pre = 1 ;
rep(i,0,m){
int x,a,b,c, k;
cin>>x>>a>> b>> c;
pre%=c;
k = 1+(a*pre%c+b)%c;
if(k> s[T[x]] ) pre = 1ll*sum[T[x]];
else pre=qr(T[x],k,1,sz(vv));
cout << pre << endl;
}
return 0;
}
转载于:https://www.cnblogs.com/seast90/p/10835205.html
