喜欢的话就坚持吧

10月 20

0.00 avg. rating (0% score) - 0 votes

题目大意

农夫有一群奶牛,起初每头奶牛的奶产量是一定的。
农夫为了记录奶牛的奶产量,写了一个表格。表格有n行,每行有3个数表示分别表示日期(在整数1…10^6范围内),奶牛的编号(在整数1…10^9范围内),该奶牛的产奶量变化值。
为了鼓励奶牛的产奶,农夫会把产量最高的奶牛照片挂在墙上(奶量相同都挂),问根据记录的表格,推算出农夫移动照片的次数,(每次记录后如果移动多头奶牛的照片算一次,就是你记录后如果你重整照片,ans++)
n<=1e5


首先这破英文体面读了我半天,发现他大概是让我维护产量最高的奶牛的集合变化了几次。
所以我们首先需要维护一个数据结构支持找最大值。
线段树?平衡树?

假设我们知道最大值是谁,我们要知道对某个值更改后,最大值是谁?
平衡树?线段树?

然后我们考虑更改某个值时,答案会如何变化。

首先,如果一个值原先是最大值然后操作后不是最大值了,答案显然++;
如果原先不是最大值,然后操作后是最大值了,答案显然++。

如果这个值更改前后都不是最大值,那么它就没用。

然后就是最后一种情况。更改前后都是最大值。
如果更改前是最大值只有一个,更改后不只一个,那么ans++;
如果更改前最大值不只一个,更改后只有一个,嘛呢ans++;

综上,我们还要维护最大值的个数。
所以你的选择是?
我选平衡树,平衡树好写。
最后说一句,发现n<=1e5 但是奶牛<=1e9.我们需要离散化。(我离散化写错还以为平衡树写错)
给你的时间排个序就行。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=300005;
const int INF=0x3f3f3f3f;

struct data
{
    int ch[2];
    int val,prio;
    int siz,cnt;
}t[N];

int pool_cur;
int root;int n,be;

inline void init(){pool_cur=0; root=0;}
inline int newnood(int val)
{
    t[++pool_cur].val=val;
    t[pool_cur].ch[0]=t[pool_cur].ch[1]=0;
    t[pool_cur].prio=rand();
    t[pool_cur].cnt=t[pool_cur].siz=1;
    return pool_cur;
}

inline void pushup(int p){t[p].siz=t[t[p].ch[0]].siz+t[t[p].ch[1]].siz+t[p].cnt;}
inline void rotate(int &p,int d)
{
    int u=t[p].ch[d];
    t[p].ch[d]=t[u].ch[d^1];
    t[u].ch[d^1]=p; 
    pushup(p);pushup(p=u);
}
inline void insert(int &p,int val)
{
    if(!p){p=newnood(val);return;}
    if(t[p].val==val){t[p].cnt++,t[p].siz++;pushup(p);return;}
    int d=t[p].val<val;
    insert(t[p].ch[d],val);++t[p].siz;
    pushup(p);
    if(t[t[p].ch[d]].prio<t[p].prio) rotate(p,d);
}
inline void remove(int &p,int val)
{
    if(!p) return;
    if(t[p].val==val)
    {
        if(t[p].cnt>1){t[p].siz--;t[p].cnt--;return;}
        if(!t[p].ch[0]){p=t[p].ch[1];return;}
        else if(!t[p].ch[1]){p=t[p].ch[0];return;}
        else 
        {
            int d=t[t[p].ch[0]].prio < t[t[p].ch[1]].prio;
            rotate(p,d^1);
            remove(t[p].ch[d],val);
        }
    }else 
    {
        int d=t[p].val<val;
        remove(t[p].ch[d],val);
    }
    pushup(p);
}
inline int fk(int p,int val)
{
    if(!p) return 0;
    if(val==t[p].val) return t[t[p].ch[1]].siz+1;
    if(val>t[p].val) return fk(t[p].ch[1],val);
    return fk(t[p].ch[0],val)+t[t[p].ch[1]].siz+t[p].cnt;
}
inline int fsiz(int p,int val)
{
    if(!p) return 0;
    if(val==t[p].val) return t[p].cnt;
    if(val>t[p].val) return fsiz(t[p].ch[1],val);
    return fsiz(t[p].ch[0],val);

}
struct project//别问我为什么又叫project
{
    int tim,num,val;
    friend bool operator <(project a,project b){return a.tim<b.tim;}
}s[N];
int b[N],tot,val[N],ans;
int main()
{
    init();
    scanf("%d%d",&n,&be);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&s[i].tim,&s[i].num,&s[i].val),b[i]=s[i].num;
    sort(s+1,s+1+n);sort(b+1,b+1+n);
    tot=unique(b+1,b+1+n)-b-1;//printf("tot=%d\n",tot);
    for(int i=1;i<=tot;++i) val[i]=be;//,printf("be=%d\n",be);
    insert(root,be);t[1].cnt=1e9;
    for(int i=1;i<=n;++i)
    {
        if(s[i].val==0) continue;
        int tm=lower_bound(b+1,b+1+tot,s[i].num)-b;
        //int tm=s[i].num;
        int rank=fk(root,val[tm]);int lsiz=fsiz(root,val[tm]);
        remove(root,val[tm]);
        val[tm]+=s[i].val;insert(root,val[tm]);
        int rank1=fk(root,val[tm]);int nsiz=fsiz(root,val[tm]);

        if(rank!=rank1)
        {
            if(rank==1||rank1==1) ans++;
        }
        else if(rank==rank1&&rank==1)
        {
            if(lsiz!=nsiz) ans++;
        }

    }
    printf("%d\n",ans);
}
0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注