# 洛谷T21778 过年

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

## 输入输出样例

`6 31 5 12 3 23 4 2`

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