bzoj 3932: [CQOI2015]任务查询系统 — 主席树 / 暴力
Contents
3932: [CQOI2015]任务查询系统
Time Limit: 20 Sec Memory Limit: 512 MB
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
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
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的一个排列
Source
好不容易打完了一个主席树，然而有人说直接暴力就行。。What ？！ T_T
好吧，就当我在练习主席树好了。。
思路1： 主席树
以时刻为下标，优先级为区间建主席树。对于在一个区间[l,r]内存在的任务，可差分处理，拆成两个点，在l处出现次数加1，在r+1处出现次数减1。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define M 10000010
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll sum[M];
int ls[M],rs[M],rt[M],w[M],lim,cnt,to[M];
inline void add(int l,int r,int x,int &y,int v)
{
y=++cnt;
w[y]=w[x]+(v>0?1:-1);
sum[y]=sum[x]+v;
if(l==r) return;
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>1;
if(abs(v)>mid) add(mid+1,r,rs[x],rs[y],v);
else add(l,mid,ls[x],ls[y],v);
}
ll que(int t,int k)
{
int x=rt[t],l=1,r=lim,mid;
if(w[x]<=k) return sum[x];
ll ans=0;
while(l<r)
{
mid=(l+r)>>1;
if(w[ls[x]]>=k)
{
x=ls[x];
r=mid;
}
else
{
k-=w[ls[x]];
ans+=sum[ls[x]];
x=rs[x];
l=mid+1;
}
}
if(k) ans+=(ll)(l)*(ll)(k);
return ans;
}
struct qaz{int t,p;}q[N];
inline bool cmp(qaz a,qaz b){return a.t<b.t;}
int m,n,s,e,tp;
ll x,a,b,c,pre=1,k;
int main()
{
m=read();n=read();
for(int i=1;i<=m;i++)
{
s=read();e=read();tp=read();
lim=max(lim,tp);
q[i].t=s;q[i].p=tp;
q[i+m].t=e+1;q[i+m].p=-tp;;
}
m<<=1;
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++) add(1,lim,rt[i-1],rt[i],q[i].p);
for(int i=m;i>0;i--) if(q[i].t!=q[i+1].t) to[q[i].t]=i;
for(int i=1;i<=n;i++) if(!to[i]) to[i]=to[i-1];
for(int i=0;i<n;i++)
{
x=read();a=read();b=read();c=read();
k=(a*pre+b)%c;
k++;
pre=que(to[x],k);
printf("%lld\n",pre);
}
}
思路2：暴力。。。
#include<cstdio>
#include<algorithm>
#define M 100010
#define ll long long
int n,m,x,a,b,c,k;
ll pre=1;
struct qaz{int s,e,p;}D[M];
bool cmp(qaz a,qaz b){return a.p<b.p;}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) scanf("%d%d%d",&D[i].s,&D[i].e,&D[i].p);
std::sort(1+D,1+m+D,cmp);
while(n--)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=1+(a*pre%c+b)%c;pre=0;
int d=0;
for(int i=1;i<=m&&d<k;i++)
if(D[i].s<=x&&D[i].e>=x){pre+=D[i].p;d++;}
printf("%lld\n",pre);
}
return 0;
}
发表评论