bzoj 3932 [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的一个排列

【思路】

以时刻为下标,优先级为区间建主席树。对于在一个区间[l,r]内存在的任务,在l处出现次数加1,在r+1处出现次数减1,把这些看作事件,将时刻i所有发生的时间加入i的线段树。然后就可以在T[x]上统计答案了。

需要注意的是时刻是连续的,所以每一个时刻都要先把上一个时刻的T复制过来。

【代码】

 #include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 1e5+;
const int M = *N; struct Node {
int lc,rc,cnt;
ll sum;
Node() {}
}T[M]; int n,m,sz;
int rt[N],mark[M],kase;
vector<int> L[N],R[N]; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} void newnode(int& y,int x)
{
T[y=++sz]=T[x]; mark[y]=kase;
}
void update(int l,int r,int x,int& y,int v,int c)
{
if(mark[x]!=kase)
newnode(y,x);
T[y].cnt+=c; T[y].sum+=v*c;
if(l==r) return ;
int mid=(l+r)>>;
if(v<=mid) update(l,mid,T[x].lc,T[y].lc,v,c);
else update(mid+,r,T[x].rc,T[y].rc,v,c);
}
ll query(int l,int r,int x,int rk)
{
if(l==r) return (ll)l*rk;
int mid=(l+r)>>;
if(T[T[x].lc].cnt>=rk) return query(l,mid,T[x].lc,rk);
else return query(mid+,r,T[x].rc,rk-T[T[x].lc].cnt)+T[T[x].lc].sum;
}
int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
n=read(),m=read();
int s,e,p,mn=1e9,mx=-1e9;
FOR(i,,n) {
s=read(),e=read(),p=read();
mn=min(mn,s),mx=max(mx,e);
L[s].push_back(p); R[e].push_back(p);
}
FOR(i,mn,mx) {
newnode(rt[i],rt[i-]); ++kase;
FOR(j,,(int)L[i].size()-) {
update(,1e7,rt[i],rt[i],L[i][j],);
}
FOR(j,,(int)R[i-].size()-)
update(,1e7,rt[i],rt[i],R[i-][j],-);
}
int x; ll a,b,c,pre=;
FOR(i,,m) {
x=read(),a=read(),b=read(),c=read();
int k=(int) +(a*pre+b)%c;
if(T[rt[x]].cnt<=k) printf("%lld\n",pre=T[rt[x]].sum);
else printf("%lld\n",pre=query(,1e7,rt[x],k));
}
return ;
}
上一篇:HDU 1788 Chinese remainder theorem again


下一篇:使用Mybatis-Generator自动生成Dao、Model、Mapping相关文件