【BZOJ3932】[CQOI2015]任務查詢系統 主席樹

【BZOJ3932】[CQOI2015]任務查詢系統

Description

最近實驗室正在為其管理的超級計算機編制一套任務管理系統，而你被安排完成其中的查詢部分。超級計算機中的

任務用三元組(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任務從第Si秒開始，在第Ei秒后結束（第Si秒和Ei秒任務也在運行

），其優先級為Pi。同一時間可能有多個任務同時執行，它們的優先級可能相同，也可能不同。調度系統會經常向

查詢系統詢問，第Xi秒正在運行的任務中，優先級最小的Ki個任務（即將任務按照優先級從小到大排序后取前Ki個

）的優先級之和是多少。特別的，如果Ki大于第Xi秒正在運行的任務總數，則直接回答第Xi秒正在運行的任務優先

級之和。上述所有參數均為整數，時間的范圍在1到n之間（包含1和n）。

Input

輸入文件第一行包含兩個空格分開的正整數m和n，分別表示任務總數和時間范圍。接下來m行，每行包含三個空格

分開的正整數Si、Ei和Pi(Si≤Ei)，描述一個任務。接下來n行，每行包含四個空格分開的整數Xi、Ai、Bi和Ci，

描述一次查詢。查詢的參數Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci計算得到。其中Pre表示上一次查詢的結果，

對于第一次查詢，Pre=1。

Output

輸出共n行，每行一個整數，表示查詢結果。

Sample Input

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

Sample Output

2
8
11

HINT

樣例解釋

K1 = (1*1+3)%2+1 = 1

K2 = (1*2+3)%4+1 = 2

K3 = (2*8+4)%3+1 = 3

對于100%的數據，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi為1到n的一個排列

題解：本題是主席樹的一個簡化版吧，我們還是先離散化，然后按時間排序，每有一個任務開始或結束就新建一棵線段樹，然后再查詢時二分查找時間，然后再線段樹上求前k個之和就行了，并且本題的主席樹是不用相減的（這還叫主席樹嗎）

注意一下long long，注意二分邊界不要搞錯（尤其是用upper_bound的童鞋們），還要注意用離散化后的數來求出答案，還有第47行有點坑人

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn=200010;
ll n,m,tot,nm,ans;
struct task
{ll pt,pv,pk;
}p[maxn];
ll ls[40*maxn],rs[40*maxn],sum[40*maxn],siz[40*maxn];
ll rp[maxn>>1],root[maxn];
bool cmp1(task a,task b)
{return a.pv<b.pv;
}
bool cmp2(task a,task b)
{return a.pt<b.pt;
}
ll readin()
{ll ret=0,f=1;   char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f;gc=getchar();}while(gc>='0'&&gc<='9')   ret=ret*10+gc-'0',gc=getchar();return ret*f;
}
void insert(ll x,ll &y,ll l,ll r,ll pos,ll val)
{y=++tot;if(l==r){siz[y]=siz[x]+val;sum[y]=sum[x]+rp[l]*val;return ;}ll mid=l+r>>1;if(pos<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,pos,val);else    ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,pos,val);siz[y]=siz[ls[y]]+siz[rs[y]];sum[y]=sum[ls[y]]+sum[rs[y]];
}
ll query(ll x,ll l,ll r,ll pos)
{if(l==r)    return rp[l]*pos;ll mid=l+r>>1;if(siz[ls[x]]>=pos)  return query(ls[x],l,mid,pos);else    return sum[ls[x]]+query(rs[x],mid+1,r,pos-siz[ls[x]]);
}
int main()
{n=readin(),m=readin();ll i,a,b,c,d,e;for(i=1;i<=n;i++)p[i*2-1].pt=readin(),p[i*2].pt=readin()+1,p[i*2-1].pv=p[i*2].pv=readin(),p[i*2-1].pk=1,p[i*2].pk=-1;sort(p+1,p+2*n+1,cmp1);for(i=1;i<=2*n;i++){if(rp[nm]<p[i].pv)   rp[++nm]=p[i].pv;p[i].pv=nm;}sort(p+1,p+2*n+1,cmp2);for(i=1;i<=2*n;i++)insert(root[i-1],root[i],1,nm,p[i].pv,p[i].pk);ans=1;for(i=1;i<=m;i++){d=readin(),a=readin(),b=readin(),c=readin();e=1+(a*ans+b)%c;ll l=1,r=2*n+1,mid;while(l<r){mid=l+r>>1;if(p[mid].pt<=d) l=mid+1;else    r=mid;}l--;if(siz[root[l]]<=e)  ans=sum[root[l]];else    ans=query(root[l],1,nm,e);printf("%lld\n",ans);}return 0;
}