A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3932[CQOI2015]任务查询系统
发表于: | 分类: Oi | 评论:0 | 阅读:44

多次进行区间加入一个值的操作,对于每一个点有一个查询该点的所有值里面第K小的是谁
强制在线

讲道理,我第一眼看过去就是权值线段树套线段树+二分答案的裸题
分析了一下好像空间还是比较虚 ,所以换一个做法

由于最开始的所有操作在一起,然后询问在一起,考虑先建出数据结构再离线查询
显然先差分标记再主席树就行了
要是说到这还没懂请看代码,要是代码还没懂请留言

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100000+5;
const int M = N << 1;
const int Maxm = 8000005;
typedef long long LL;
using namespace std;

int head[N];

struct graph
{
    int next,to;bool val;
    graph () {}
    graph (int _next,int _to,bool _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,bool z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
}

LL tr[Maxm];
int cnt[Maxm],ls[Maxm],rs[Maxm],root[N],sz;

void change(int L,int R,int x,int &y,int pos,int val)
{
    y = ++sz; rs[y] = rs[x],ls[y] = ls[x];
    cnt[y] = cnt[x] + val; tr[y] = tr[x] + (LL)val*pos;
    if(L == R) return;
    int mid = (L+R) >> 1;
    if(pos <= mid) change(L,mid,ls[x],ls[y],pos,val);
    else change(mid+1,R,rs[x],rs[y],pos,val);
}

LL find(int y,int rank,int L,int R)
{
    if(!cnt[y] || !rank) return 0;
    if(L == R) 
        return tr[y]/cnt[y]*rank;
    int mid = (L+R) >> 1, tt = cnt[ls[y]] ;
    if(rank <= tt) return find(ls[y],rank,L,mid);
    else return tr[ls[y]] + find(rs[y],rank-tt,mid+1,R);
}

inline int read()
{
    int 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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{

    int m = read(), n = read();

    for(int i=1;i<=m;++i)
    {
        int x = read(), y = read()+1, z = read();
        add(x,z,1);
        add(y,z,0);
    }

    for(int i=1;i<=n;++i)
    {
        root[i] = root[i-1];
        for(int j=head[i];j;j=edge[j].next)
            change(1,10000000+5,root[i],root[i],edge[j].to,(edge[j].val == 0 ? -1 : 1));
    }

    LL lastans = 1;
    int times,A,B,C;
    for(int i=1;i<=n;++i)
    {
        times = read(), A = read(), B = read(), C = read();
        A = ((long long)A * lastans + B)%C + 1;
        printf("%lld\n",lastans = find(root[times],A,1,10000000+5));
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP