题解 P3168 【[CQOI2015]任务查询系统】

· · 题解

主席树题，做差分统计，在差分树上操作，一边操作一边“滚动”。仅当i时刻的所有操作结束，将i作为i+1的原版。

统计答案时在线段树上二分就可以。注意一点，可能存在相同的优先级，比如说优先级可以使 2 3 3 4 6，这样查K = 2的时候答案不是值域线段树上2和3的位置的SUM，而是2的SUM加上剩余排名个数个3，详见代码。

离散化，数据太大了，我用的是sort+unique+map，清一色的STL，map有点慢，注意一下，能少用就少用，一开始就因为map所以TLE好久……

至于空间范围，告诉你们，很大，原题应该是512MB，不知道这里是多少，起码8*10^6没有问题，不要开到4*10^6以下，那样就RE了。

好了，各种问题都说了，不要问我怎么知道的，看看提交记录。

下面是代码。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define MAXT 8000000
#define MAXN 100000
#define ll long long
#define lc(x) t[x].lc
#define rc(x) t[x].rc
#define mx(x) t[x].mx
#define sum(x) t[x].sum
#define mid ((lef+rig)>>1)
#define sgn(x) (x > 0 ? 1 : -1) 
struct Node
{
    ll mx,sum;
    int lc,rc;
    Node(){}
    Node(ll a, ll b)
    {
        mx = a, sum = b;
        return;
    }
};
ll dat[MAXN*4+5], tot, Pre = 1, n, k, op, tm, s, e, p;
Node t[MAXT+5];
map<ll,ll> h;
struct Segment_Tree
{
    int root;
    inline Node Merge(Node a, Node b)
    {
        a.mx += b.mx, a.sum += b.sum;
        return a;
    }
    inline void Push(int p)
    {
        mx(p) = mx(lc(p)) + mx(rc(p)), sum(p) = sum(lc(p)) + sum(rc(p));
        return;
    }
    inline void Init(int x = -1)
    {
        root = tot++;
        if(x+1)
            t[root] = t[x];
        return;
    }
    Node Query(int p, int lef, int rig, int L, int R)
    {
        if(!p || lef > rig)
            return Node(0ll,0ll);
        if(L == lef && R == rig)
            return t[p];
        if(R <= mid)
            return Query(lc(p),lef,mid,L,R);
        if(L >  mid)
            return Query(rc(p),mid+1,rig,L,R);
        return Merge(Query(lc(p),lef,mid,L,mid) , Query(rc(p),mid+1,rig,mid+1,R)); 
    }
    void Edit(int p, int lef, int rig, int x, int tag)
    {
        if(lef == rig)
        {
            mx(p) += tag, sum(p) += tag*dat[lef];
            return;
        }    
        int temp = tot++;
        if(x <= mid)
            t[temp] = t[lc(p)], lc(p) = temp, Edit(lc(p),lef,mid,x,tag);
        else
            t[temp] = t[rc(p)], rc(p) = temp, Edit(rc(p),mid+1,rig,x,tag);
        Push(p);
        return;
    }
};
Segment_Tree T[MAXN+5];
struct Task
{
    ll pos,val;    
}X[MAXN*2+5];
inline bool operator < (Task a, Task b)
{
    return a.pos < b.pos;
}
inline ll Search(ll ti, ll rank)
{
    ll lef = 1, rig = k;
    for(Node midd; lef < rig; )
    {
        midd = T[ti].Query(T[ti].root,1,k,1,mid);
        if(midd.mx >= rank)
            rig = mid;
        else
            lef = mid+1;
    }
    Node res = T[ti].Query(T[ti].root,1,k,1,lef-1);
    Node poi = T[ti].Query(T[ti].root,1,k,lef,lef);
    Pre = res.sum;
    if(rank <= res.mx+poi.mx)
        Pre += dat[lef]*(rank-res.mx);
    return Pre;
}
inline ll read()
{
    ll ans=0;    
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9') last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
void out(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)
        putchar(x+'0');
    else{
        out(x/10);
        putchar(x%10+'0');
    }
    return;
}
int main()
{
    n = read(), tm = read();
    for(register int i = op = k = 1; i <= n; i++)
        s = read(), e = read(), p = read(), dat[k++] = p,
        X[op].pos = s, X[op++].val = p, X[op].pos = e+1, X[op++].val = -p;
    sort(X+1,X+op), op--, sort(dat+1,dat+k), k = unique(dat+1,dat+k)-dat-1;
    for(register int i = 1; i <= k; i++)
        h[dat[i]] = i;
    T[0].Init();
    for(register int i = 1, j = 1; i <= tm; i++)
    {
        T[i].Init(T[i-1].root);
        for(; X[j].pos == i; j++)
            T[i].Edit(T[i].root,1,k,h[abs(X[j].val)],sgn(X[j].val));
    }
    for(ll x, a, b, c; tm--; out(Search(x,1+(a*Pre+b)%c)),putchar('\n'))
        x = read(), a = read(), b = read(), c = read();
     return 0;
}
看到有些代码，没用主席树，直接奇迹般暴力O（nm）水过了。敲了3个小时的我表示无语。