[CQOI2015]任务查询系统

#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;
}