洛谷T21778 过年

题目描述

有 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 3
1 5 1
2 3 2
3 4 2

输出样例#1: 

1
1
2
1
1
-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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1400 塔

    题目描述 有N(2<=N<=600000)块砖,要搭一个N层的塔,要求:如果砖A在砖B上面,那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 10...

    attack
  • CSU1216: 异或最大值(01Trie树)

    多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

    attack
  • BZOJ3265: 志愿者招募加强版(线性规划)

    attack
  • P1400 塔

    题目描述 有N(2<=N<=600000)块砖,要搭一个N层的塔,要求:如果砖A在砖B上面,那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 10...

    attack
  • loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

    attack
  • BZOJ3265: 志愿者招募加强版(线性规划)

    attack
  • codechef September Challenge 2018 Division 2 A-F

    最大的是:$2, 3, 4, 5, n / 2, 1, 2 + n / 2, 3 + n / 2, 4 + n  /2 ...$

    attack
  • 洛谷P2447 [SDOI2010]外星千足虫(异或方程组)

    找最优解可以考虑高斯消元的过程,因为异或的特殊性质,每次向下找的时候找到第一个1然后交换就行,这样显然是最优的

    attack
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • 洛谷P1941 飞扬的小鸟(背包 dp)

    很显然的dp,设\(f[i][j]\)表示第\(i\)个位置,高度为\(j\)的最小步数

    attack

扫码关注云+社区

领取腾讯云代金券