P3168 [CQOI2015]任务查询系统
题目描述
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。
超级计算机中的任务用三元组\((S_i,E_i,P_i)\)描述，\((S_i,E_i,P_i)\)表示任务从第\(S_i\)秒开始，在第\(E_i\)秒后结束（第\(S_i\)秒和\(E_i\)秒任务也在运行），其优先级为\(P_i\)。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。
调度系统会经常向查询系统询问，第\(X_i\)秒正在运行的任务中，优先级最小的\(K_i\)个任务（即将任务按照优先级从小到大排序后取前\(K_i\)个）的优先级之和是多少。
特别的，如果\(K_i\)大于第\(X_i\)秒正在运行的任务总数，则直接回答第\(X_i\)秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在\(1\)到\(n\)之间（包含\(1\)和\(n\)）。
输入输出格式
输入格式：
输入文件第一行包含两个空格分开的正整数\(m\)和\(n\)，分别表示任务总数和时间范围。
接下来m行，每行包含三个空格分开的正整数\(S_i\)、\(E_i\)和\(P_i(S_i<=E_i)\)，描述一个任务。接下来\(n\)行，每行包含四个空格分开的整数\(X_i\)、\(A_i\)、\(B_i\)和\(C_i\)，描述一次查询。
查询的参数\(K_i\)需要由公式 \(K_i=1+(A_i*Pre+B_i) \ mod \ C_i\)计算得到。其中\(Pre\)表示上一次查询的结果，对于第一次查询，\(Pre=1\)。
输出格式：
输出共\(n\)行，每行一个整数，表示查询结果。
说明
对于100%的数据，\(1<=m,n,S_i,E_i,C_i<=100000\)，\(0<=A_i,B_i<=100000\)，\(1<=P_i<=10000000\)，\(X_i\)为\(1\)到\(n\)的一个排列
时空范围：2sec,256mb
化简模型，给出\(m\)个三元组\((s,e,p)\)
询问\((x,k)\)为满足\(s \le x \le e\)的三元组的前\(k\)大\(p\)值之和，强制在线
一看是一个偏序类题目，我们可以多维数据结构暴力嵌套，这个题最多允许\(log^2\),又有第\(k\)大询问，自然的想到主席树降维
使用树状树状套主席树求解
其中树状树状的区间代表从大到小排序的\(E_i\)
树状树状的每个区间放对应的一群线段树，我们先对区间按\(S_i\)从小到大排序，然后按这个顺序建主席树就行了
主席树的节点存离散（不离散似乎也过了）的\(p_i\)值，注意维护一下区间和
查询的时候，在每个树状数组对应的主席树上一起二分即可，注意重复的元素
Code
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node
{
int s,t,p;
bool friend operator <(node n1,node n2){return n1.t>n2.t;}
}rask[N];
struct RT
{
int s,now;
RT(){}
RT(int s,int now){this->s=s,this->now=now;}
bool friend operator <(RT n1,RT n2){return n1.s<n2.s;}
}rt;
vector <RT> root[N];
int cnt[N*244],ch[N*244][2],tot,n,m,mxx;ll sum[N*244];
int max(int x,int y){return x>y?x:y;}
#define ls ch[now][0]
#define rs ch[now][1]
#define ols ch[las][0]
#define ors ch[las][1]
void update(int now)
{
sum[now]=sum[ls]+sum[rs];
cnt[now]=cnt[ls]+cnt[rs];
}
int build(int las,int l,int r,int pos)
{
int now=++tot;
if(l==r)
{
cnt[now]=cnt[las]+1;
sum[now]=1ll*cnt[now]*l;
return now;
}
int mid=l+r>>1;
if(pos<=mid)
{
ls=build(ols,l,mid,pos);
rs=ors;
}
else
{
ls=ols;
rs=build(ors,mid+1,r,pos);
}
update(now);
return now;
}
void init()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&rask[i].s,&rask[i].t,&rask[i].p),mxx=max(mxx,rask[i].p);
sort(rask+1,rask+1+m);
for(int i=1;i<=m;i++)
{
for(int j=i-(i&-i)+1;j<=i;j++)
{
rt=RT(rask[j].s,j);
root[i].push_back(rt);
}
sort(root[i].begin(),root[i].end());
for(int las=0,j=0;j<root[i].size();j++)
las=root[i][j].now=build(las,1,mxx,rask[root[i][j].now].p);
}
}
ll query(int x,int pos,int k)//时间，前pos可查，第k值
{
int now[50],p=0;
for(int i=pos;i;i-=i&-i)
{
RT t=RT(x,0);
int j=upper_bound(root[i].begin(),root[i].end(),t)-root[i].begin()-1;
now[++p]=root[i][j].now;
}
int l=1,r=mxx;ll ans=0;
while(l<r)
{
int mid=l+r>>1,s=0;
for(int i=1;i<=p;i++) s+=cnt[ch[now[i]][0]];
if(s>=k)
{
for(int i=1;i<=p;i++) now[i]=ch[now[i]][0];
r=mid;
}
else
{
for(int i=1;i<=p;i++) ans+=sum[ch[now[i]][0]],now[i]=ch[now[i]][1];
l=mid+1,k-=s;
}
}
int cnt0=0;
for(int i=1;i<=p;i++) cnt0+=cnt[now[i]];
ans+=1ll*l*min(cnt0,k);
return ans;
}
void work()
{
ll pre=1;
for(int pos,x,a,b,c,k,i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=(a*(int)(pre%(1ll*c))+b)%c+1;
node t={0,x,0};
pos=upper_bound(rask+1,rask+1+m,t)-rask-1;
printf("%lld\n",pre=query(x,pos,k));
}
}
int main()
{
init(),work();
return 0;
}
然而，我们注意到这个问题有这样一个暴力
对操作，我们可以把每个对应位置上都加上这个优先级，并用权值线段树维护
然后查询时，直接进入对应位置的权值线段树查询即可
而事实上，我们发现这是对每个位置有一个区间加，我们可以采用差分数组的思想
把三元组\((s,e,p)\)的\(s\)位置的\(p\)值\(+1\)，把\(e+1\)位置\(p\)值\(-1\)（这里\(p\)值在对于位置的权值线段树上）
然后我们查询的时候，就求这些权值线段树的前缀和就可以了
这不就是主席树干的事情吗
于是乎问题就可以直接用主席树做了
Code:
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node{int s,e,p;}rask[N];
int a[N];
int cnt[N*100],ch[N*100][2],root[N],tot,n,m,num;ll sum[N*100];
#define ls ch[now][0]
#define rs ch[now][1]
void updata(int now)
{
sum[now]=sum[ls]+sum[rs];
cnt[now]=cnt[ls]+cnt[rs];
}
void build(int &now,int l,int r,int pos,int del)
{
if(!now) now=++tot;
if(l==r)
{
cnt[now]+=del;
sum[now]=1ll*cnt[now]*a[l];
return;
}
int mid=l+r>>1;
if(pos<=mid)
build(ls,l,mid,pos,del);
else
build(rs,mid+1,r,pos,del);
updata(now);
}
int rebuild(int x,int y)
{
if(!x||!y) return x+y;
int now=++tot;
sum[now]=sum[x]+sum[y];
cnt[now]=cnt[x]+cnt[y];
ls=rebuild(ch[x][0],ch[y][0]);
rs=rebuild(ch[x][1],ch[y][1]);
return now;
}
void init()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&rask[i].s,&rask[i].e,&rask[i].p);
a[i]=rask[i].p;
}
sort(a+1,a+1+m);
++n;
num=unique(a+1,a+1+m)-a-1;
for(int i=1;i<=m;i++)
{
rask[i].p=lower_bound(a+1,a+1+num,rask[i].p)-a;
build(root[rask[i].s],1,num,rask[i].p,1);
build(root[rask[i].e+1],1,num,rask[i].p,-1);
}
for(int i=1;i<=n;i++)
root[i]=rebuild(root[i-1],root[i]);
}
ll query(int now,int l,int r,int k)
{
if(l==r)
return 1ll*a[l]*min(k,cnt[now]);
int mid=l+r>>1;
if(cnt[ls]>=k) return query(ls,l,mid,k);
else return sum[ls]+query(rs,mid+1,r,k-cnt[ls]);
}
void work()
{
ll pre=1;
for(int x,a,b,c,k,i=1;i<n;i++)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=(a*(int)(pre%(1ll*c))+b)%c+1;
printf("%lld\n",pre=query(root[x],1,num,k));
}
}
int main()
{
init(),work();
return 0;
}
2018.9.13