洛谷T21778 过年

2018-02-10 13:07:51来源:cnblogs.com作者:自为风月马前卒人点击

分享

题目描述

有 n(1 /leq n /leq 10^5)n(1≤n≤105) 个小朋友,过年了,要发放 m(1 /leq m /leq 10^5)m(1≤m≤105) 次礼物。

每次发放,会给出三个参数 l,r,k(1 /leq l /leq r /leq n, 1 /leq k /leq 10^5)l,r,k(1≤l≤r≤n,1≤k≤105) ,表示给区间 [l, r][l,r] 内的小朋友都发一个礼物 kk 。

所有礼物发放完成后,对于每一个小朋友,回答他接受的礼物中,出现次数最多的礼物是什么。如果有多个,输出编号最小的那个;如果不存在,输出 -1−1 。

输入输出格式

输入格式:

第一行两个整数 n, mn,m ,意义如上所述。

接下来 mm 行,每行三个数 l,r,kl,r,k ,意义如上所述。

输出格式:

一共 nn 行,每行一个数,表示答案。

输入输出样例

输入样例#1: 复制
6 31 5 12 3 23 4 2
输出样例#1: 复制
11211-1


思路比较无脑,全是套路类的问题
按照小盆友的序号建权值线段树
对于每个询问差分一下
在树上打标记,记录最大值和最大值的位置
emmm以后要考虑考虑线段树怎么写了,感觉用DFS序不仅内存小,还写着顺手

// luogu-judger-enable-o2#include<iostream>#include<vector>#include<cstdio>using namespace std;const int MAXN=1e6+10;struct node{    int l,r,ls,rs,mx,mxpos;}T[MAXN];vector<int>v[MAXN];int root,tot;void Build(int &k , int ll , int rr){    k=tot++;    T[k].mx=0; T[k].l = ll ; T[k].r = rr;    if( ll == rr  ) { T[k].mxpos = ll; return ; }    int mid=ll + rr >>1;    Build( T[k].ls , ll , mid );    Build( T[k].rs , mid+1 , rr );}void update(int k){    if( T[ T[k].ls ].mx >= T[ T[k].rs ].mx ) T[k].mx = T[ T[k].ls ].mx , T[k].mxpos = T[ T[k].ls ].mxpos;    else                                     T[k].mx = T[ T[k].rs ].mx , T[k].mxpos = T[ T[k].rs ].mxpos;}void Add(int k, int pos ){    if( T[k].l == T[k].r )    {        T[k].mx++;        return ;    }    int mid=T[k].l + T[k].r >>1;    if(pos<=mid) Add( T[k].ls , pos );    else          Add( T[k].rs , pos );    update(k);}void Delet(int k, int pos ){    if( T[k].l == T[k].r )    {        T[k].mx--;        return ;    }    int mid= T[k].l + T[k].r >>1;    if(pos<=mid) Delet( T[k].ls , pos );    else          Delet( T[k].rs , pos );    update(k);}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    int N,M;    scanf("%d%d",&N,&M);    for(int i=1; i<=M ;i++ )    {        int l,r,k;        scanf("%d%d%d",&l,&r,&k);        v[l].push_back(k);        v[r+1].push_back(-k);    }    Build(root,1,N);    for(int i=1; i<=N ;i++)    {        for(int j=0; j<v[i].size() ;j++ )        {        //    printf("*%d*",v[i][j]);            if( v[i][j]>0 )                 Add(root , v[i][j] );            if( v[i][j]<0 )                 Delet(root , -v[i][j] );         }         if( T[root].mx )              printf("%d/n",T[ root ].mxpos );        else            printf("-1/n");    }        return 0;}



最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台