題目大意：
最近實驗室正在為其管理的超級計算機編制一套任務管理系統，而你被安排完成其中的查詢部分。超級計算機中的 任務用三元組(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任務從第Si秒開始，在第Ei秒後結束（第Si秒和Ei秒任務也在運行 ），其優先級為Pi。同一時間可能有多個任務同時執行，它們的優先級可能相同，也可能不同。調度系統會經常向 查詢系統詢問，第Xi秒正在運行的任務中，優先級最小的Ki個任務（即將任務按照優先級從小到大排序後取前Ki個 ）的優先級之和是多少。特別的，如果Ki大於第Xi秒正在運行的任務總數，則直接回答第Xi秒正在運行的任務優先 級之和。上述所有參數均為整數，時間的范圍在1到n之間（包含1和n）。 思路： 先將優先值離散，然後對每個時間建一棵記錄當前時間正在運行的優先值為l~r的任務的個數、優先值之和的線段樹，顯然可以用主席樹優化。一個從s到t的任務可以看成在s時間發生，在t+1時間結束，於是一個任務只需要在s和t+1更新。 對於查找，判斷當前要找的k和左子樹任務個數的大小關系，如果k大，查詢右子樹，否則查詢左子樹。注意當l==r時返回要注意k的值。 代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100001
#define ll long long
inline void Read(long long& x){
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar());
}
inline void Read(int& x){
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar());
}
vector<int>a1[N],a2[N];
struct node{
int l,r,s;
ll w;
}c[N*80];
struct gj{
int x,y,z;
}b[N];
struct ls{
int w,f;
}a[N];
int i,j,Rt[N],k,Num,n,m,M;
ll Last=1,w2[N],x,y,z;
inline void Update(int& Node,int l,int r,int x,int y){
c[++Num]=c[Node];Node=Num;
c[Node].w+=w2[x]*y;c[Node].s+=y;
if(l==r)return;
int Mid=(l+r)>>1;
if(x<=Mid)Update(c[Node].l,l,Mid,x,y);else Update(c[Node].r,Mid+1,r,x,y);
}
inline ll Query(int Node,int l,int r,int x){
if(l==r)return c[Node].w/c[Node].s*x;
int Mid=(l+r)>>1;
if(c[c[Node].l].s>x)return Query(c[Node].l,l,Mid,x);else if(c[c[Node].l].s==x)return c[c[Node].l].w;else return Query(c[Node].r,Mid+1,r,x-c[c[Node].l].s)+c[c[Node].l].w;
}
inline bool Cmp(ls a,ls b){
return a.w<b.w;
}
int main()
{
Read(m);Read(n);
for(i=1;i<=m;i++)Read(b[i].x),Read(b[i].y),Read(b[i].z),a[i].w=b[i].z,a[i].f=i;
sort(a+1,a+m+1,Cmp);
for(i=1;i<=m;i++)if(a[i].w==a[i-1].w)b[a[i].f].z=M;else b[a[i].f].z=++M,w2[M]=a[i].w;
for(i=1;i<=m;i++){
a1[b[i].x].push_back(b[i].z);a2[b[i].y+1].push_back(b[i].z);
}
for(i=1;i<=n;i++){
Rt[i]=Rt[i-1];
for(j=0;j<a1[i].size();j++)Update(Rt[i],1,M,a1[i][j],1);
for(j=0;j<a2[i].size();j++)Update(Rt[i],1,M,a2[i][j],-1);
}
for(i=1;i<=n;i++){
Read(k);Read(x);Read(y);Read(z);
x=((x*Last+y)%z)+1;
if(c[Rt[k]].s<=x)Last=c[Rt[k]].w;else Last=Query(Rt[k],1,M,x);
printf("%lld\n",Last);
}
return 0;
}
bzoj3932
