[CQOI2015]任务查询系统

BZOJ3932
 
啊...我的程序跑了足足15s...真是弱爆了。很好奇第一名1K+的代码量1s是怎么做到的...
总之我的作法就是对时间维护一个树状数组套权值线段树。
这里有一个树状数组的妙用,传统的树状数组是单点修改,区间询问。这里我们把它变成区间修改,单点询问,同样是利用元素的可加性:
直接把每次询问变成询问前缀,方法就是添加的时候只在左端点添加,并在右端点的后一个减去。
 
然后这样时间复杂度是O(n * log^2(m) + m * log^2(K))的...
 
源代码如下:
 

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <time.h>

 

typedef long long Long;

 

const int Len = 200000;

 

int N = 0;//num of elements in P

 

int num_ask = 0;

 

int P[Len + 100];//[]

 

struct node

{

    int l;

    int r;

    int num;

    Long sum;

    int lson;

    int rson;

    node()

    {}

    node(int L,int R)

    {

        l = L;

        r = R;

        num = 0;

        sum = 0;

        lson = 0;

        rson = 0;

    }

};

 

node nodes[Len * 80];

int tot = 1;

 

struct ChairTree

{

    int head;

    ChairTree()

    {

        head = 0;

    }

    void add(int a,int k)

    {

        if(!head)

        {

            head = tot;

            tot++;

            nodes[head] = node(1,N);

        }

         

        _add(head,a,k);

    }

 

    void _add(int n,int a,int k)

    {

        while(1)

        {

            nodes[n].num += k;

            nodes[n].sum += 1LL * k * a;

     

            if(nodes[n].l == nodes[n].r)

                break;

     

            int mid = (((nodes[n].l) + (nodes[n].r)) >> 1);

     

            if(a <= P[mid])

            {

                if(!(nodes[n].lson))

                {

                    nodes[n].lson = tot;

                    tot++;

                    nodes[nodes[n].lson] = node(nodes[n].l,mid);

                }

                n = nodes[n].lson;

                continue;

            }

            else

            {

                if(!(nodes[n].rson))

                {

                    nodes[n].rson = tot;

                    tot++;

                    nodes[nodes[n].rson] = node(mid + 1,nodes[n].r);

                }

                n = nodes[n].rson;

                continue;

            }

        }

    }

};

 

int ta_len = 0;

ChairTree ta[Len + 10];

inline void add(int p,int n,int k)//在p处加入k个n

{

    for(int i = p;i <= ta_len;i += (i & (-i)))

    {

        ta[i].add(n,k);

    }

}

 

int cts[Len + 10];

int ctst = 0;

inline void ask(int p)

{

    ctst = 0;

    for(int i = p;i >= 1;i -= (i & (-i)))

        cts[ctst++] = ta[i].head;

}

 

inline Long get_ans(int k)

{

    Long result = 0;

    while(1)

    {

        bool find_1 = false;

        int can = 0;

        int num = 0;

        Long sum = 0;

        int num_lson = 0;

        int num_rson = 0;

        Long sum_lson = 0;

        Long sum_rson = 0;

         

        for(int i = 0;i < ctst;i++)

        {

            if(cts[i])

            {

                find_1 = true;

                can = i;

                if(nodes[cts[i]].lson)

                {

                    num_lson += nodes[nodes[cts[i]].lson].num;

                    sum_lson += nodes[nodes[cts[i]].lson].sum;

                }

                if(nodes[cts[i]].rson)

                {

                    num_rson += nodes[nodes[cts[i]].rson].num;

                    sum_rson += nodes[nodes[cts[i]].rson].sum;

                }

                num += nodes[cts[i]].num;

                sum += nodes[cts[i]].sum;

                //fprintf(stderr,"%d %I64d\n",num_rson,sum_rson);

            }

        }

         

        //fprintf(stderr,"%d %I64d\n",k,sum);

         

        if(!find_1)

            break;

             

        if(k > num)

            k = num;

         

        if(k == num)

        {

            result += 1LL * sum;

            break;

        }

         

        if(nodes[cts[can]].l == nodes[cts[can]].r)

        {

            result += 1LL * k * (sum / num);

            break;

        }

         

        if(k <= num_lson)

        {

            for(int i = 0;i < ctst;i++)

            {

                if(cts[i])

                    cts[i] = nodes[cts[i]].lson;

            }

        }

        else

        {

            for(int i = 0;i < ctst;i++)

            {

                if(cts[i])

                    cts[i] = nodes[cts[i]].rson;

            }

            result += 1LL * sum_lson;

            k -= num_lson;

        }

    }

     

    return result;

}

 

inline void get_int(int & r)

{

    r = 0;

    char c = 0;

     

    do

    {

        c = getchar();

    }

    while(c == ' ' || c == '\n' || c == '\t');

     

    do

    {

        r *= 10;

        r += (c - '0');

        c = getchar();

    }

    while(c >= '0' && c <= '9');

}

 

struct op

{

    int l;

    int r;

    int p;

};

 

op ops[Len + 100];

 

int num_op = 0;

 

int max_time = 0;

ChairTree T;

int main()

{

    scanf("%d%d",&num_op,&num_ask);

 

    for(int i = 0;i < num_op;i++)

    {

        //scanf("%d%d%d",&ops[i].l,&ops[i].r,&ops[i].p);

        get_int(ops[i].l);

        get_int(ops[i].r);

        get_int(ops[i].p);

         

        P[++N] = ops[i].p;

    }

     

    ta_len = max_time = num_ask;

     

    std::sort(P + 1,P + 1 + N);

     

    //fprintf(stderr,"%d\n",clock());

     

    for(int i = 0;i < num_op;i++)

    {

        //printf("%d\n",i);

         

        add(ops[i].l,ops[i].p,1);

         

        if(ops[i].r < num_ask)

            add(ops[i].r + 1,ops[i].p,-1);

    }

     

    //fprintf(stderr,"%d\n",clock());

     

    int X = 0;

    int A = 0;

    int B = 0;

    int C = 0;

    Long last_ans = 1LL;

    int k = 0;

    for(int i = 0;i < num_ask;i++)

    {

        //scanf("%d%d%d%d",&X,&A,&B,&C);

        get_int(X);

        get_int(A);

        get_int(B);

        get_int(C);

         

        k = 1 + (int)((1LL * A * last_ans + 1LL * B) % (1LL * C));

         

        ask(X);

         

        last_ans = get_ans(k);

         

        //std::cout<<last_ans<<std::endl;

        printf("%lld\n",last_ans);

    }

     

    //fprintf(stderr,"%d\n",clock());

    return 0;

}