CQOI2015 任务查询系统

前言：

说实在话前言只是用来加个 read more 不让你们在看预览的时候就知道题目…

题目：

题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

输入输出格式

输入格式：

输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，对于第一次查询，Pre=1。

输出格式：

输出共n行，每行一个整数，表示查询结果。

输入输出样例

输入样例#1：

输出样例#1：

2
8
11

说明

样例解释

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

解题分析：

暴力：

暴力分析

我们来看一下这道题的暴力
时间复杂度为 O（nm ) 看样子很不可行（mmp 数据为100000…
但是我们还是要记得暴力出奇迹洛谷的数据水得可怜…凡事都是要先考虑暴力的不是吗
我用了一些（假）优化和剪枝的…
另外这道题是强制在线（？蒟蒻逃…
我们按照任务的优先级先排个序，然后每读到一个满足条件的任务就直接加上，按理说要比时间复杂度比 O（nm）低
好了我们上代码

暴力代码

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define ll long long 

using namespace std;

const int N=100010;
int n,m,num,x,y,z;
ll last=1,now;
struct mess{
    int s,e,p; 
}a[N];

inline bool cmp(mess x,mess y){
    return x.p<y.p;
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].p);
    sort(a+1,a+1+n,cmp);
    rep(i,1,m) {
        int cnt=0;ll ans=0;
        scanf("%d%d%d%d",&num,&x,&y,&z);
        now=(x*last+y)%z+1;
        rep(i,1,n){
            if(cnt>=now) break;
            else if(a[i].s<=num&&a[i].e>=num) ans+=a[i].p,cnt++;
        }
        printf("%lld\n",ans);last=ans;
    }
    return 0;
}

不开long long 70分…时间跑的很快比主席树快多了…空间也很小
我就不在这里口糊了毕竟暴力也不是什么好方法…

主席树：

正解分析

这道题的正解是主席树…暴力跑得过去说明运气好说不准明天数据就加强了要么我现在就去叫 chen_zhe…
并不是很能看的出来但是实际上加个差分就是主席树的模板了…
主席树我之前也讲过了就不多赘述了…我们现在就讲讲怎么差分
我们使前 K 大的主席树维护数据个数size和数据和val，将区间累加和的修改改成两点修改，再运用前缀和的思想
假设我们要将区间 l ~ r 各加上 k ，只要将 a [ l ]+k , a [ r+1 ]-k ,sum [ r ]=a [ 1 ] +….+ a [ r ] ，就维护好了 val
维护 size 也很简单，只需要判断在该位置上减去了几次就行了…（反正都用前缀和维护了…
另外，long long 不可少…
我好菜啊这道题我看了好久
我们来看一下代码

正解代码氧气优化1448ms

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define ll long long

using namespace std;
	
const int N=100010;
int n,m,root[N],tot=0,cnt=0;
ll ans=1,s[N],x,y,z,now,num;
struct node{
	int l,r;
    ll val,size;
}T[4*N*60];
struct prefix{
	int dis,k,type;
    inline bool operator <(const prefix &rhy)const{return dis<rhy.dis;}
}a[N*4];
	
inline void insert(int &p,int x,int type,int l,int r){
	T[++cnt]=T[p];p=cnt;T[p].size+=(ll)type;T[p].val+=(ll)type*s[x];
    if(l==r) return;
    int mid=(l+r)>>1;
	if(mid>=x) insert(T[p].l,x,type,l,mid);
    else insert(T[p].r,x,type,mid+1,r);
}
	
inline ll query(int p,int k,int l,int r){
	if(l==r) return (T[p].val/T[p].size)*(ll)k;
	int t=T[T[p].l].size,mid=(l+r)>>1;
	if(k<=t) return query(T[p].l,k,l,mid);
	else return T[T[p].l].val+query(T[p].r,k-t,mid+1,r);
}
	
int main(){
	scanf("%d%d",&n,&m);root[0]=0;
    rep(i,1,n){
        scanf("%d%d%d",&x,&y,&z);
        s[i]=z;a[++tot].dis=x,a[tot].k=z,a[tot].type=1;
	    a[++tot].dis=y+1,a[tot].k=z,a[tot].type=-1;
    }
    sort(s+1,s+1+n);sort(a+1,a+1+tot);
    for(int i=1,j=1;i<=n;i++){
        root[i]=root[i-1];
        for(;j<=tot&&a[j].dis==i;j++){
            int rk=lower_bound(s+1,s+1+n,a[j].k)-s;
	            insert(root[i],rk,a[j].type,1,n);
        }
    }
    while(m--){
        scanf("%lld%lld%lld%lld",&num,&x,&y,&z);
        now=(x*ans+y)%z+1;
        if(now>=T[root[num]].size) ans=T[root[num]].val;
        else ans=query(root[num],now,1,n);
        printf("%lld\n",ans);
    }
    return 0;
}

mmp空间开小了只有40分一开始还以为是long long的锅…
我真的菜啊准备退役…

后记：

有时候一些高级数据结构还是蛮有用的
我也不知道为什么要加个后记随便看看好了
对了欢迎指正…（我并没有在博客中加入评论…
好像博客的子数统计也不是很准…
还有一件很重要的事我菜爆了我弃坑了…哦朋友再见

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan