This page looks best with JavaScript enabled

「Luogu3765」总统选举-平衡树-线段树

 ·  ✏️ About  1285 words  ·  ☕ 3 mins read · 👀... views

秋之国共有 $n$ 个人，分别编号为 $1,2,…,n$ ，一开始每个人都投了一票，范围 $[1,n]$ ，表示支持对应编号的人当总统。共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人，没有候选人的话输出 $-1$ 。

链接

Luogu P3765

题解

非常有趣的一道题。

BZOJ的2456可以启发到这道题。

那道题是：

给你一个 $n$ 个数的数列，其中某个数出现了超过 $\frac {n}{2}$ 次即为绝对众数，请你找出那个数。

做法则是:

如果众数出现了超过 $\frac {n}{2}$ 次，那么任意删除序列中的两个不同的数，众数的出现次数仍然超过一半。不停地进行下去，最终剩下的一个数即为众数。(摘自Menci’s Blog)

这件事是可以用线段树维护的。

所以可以用线段树维护这个信息，就可以在 $O(\log {n})$ 的时间里查询到某个区间可能的区间绝对众数。可以证明，如果区间有绝对众数，那么这个数一定就是。但是也可以发现，这个数不一定就是绝对众数，所以我们需要检验。

这个时候我们建立 $n$ 棵平衡树，共用一个 $pool$ 。我们可以直接用数组中的节点编号来代表它的 $val$ 。检验的时候，找到待查询数字的根节点，然后查询在 $[l,r]$ 区间内有多少个数，也就是 $getrank(r+1) - getrank(l)$ 。然后就可以检验出给定的数是不是给定的区间的绝对众数了。

修改投票也很简单，线段树直接修改然后一路维护就好，平衡树的话就在旧树里删掉，新树里加上就可以了。

时间复杂度大概是

$$O((n+\sum _ {i = 1}^{n} {k_i}) \log {n})$$

可以过掉本题。

妙啊！

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;

namespace fast_io {
    //...
}using namespace fast_io;
const int MAXN = 550000;
int n,m,num[MAXN];

//平衡树
namespace Treap{
int nowcnt = 0;
int p[MAXN],son[MAXN][2];
int siz[MAXN];
int root[MAXN];
void update(int x){
    siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
}
void rotate(int &x,int t){
    int y = son[x][t];
    son[x][t] = son[y][1-t];
    son[y][1-t] = x;
    update(x),update(y);
    x = y;
}
void insert(int &x,int v){
    if(!x){
        x = v,p[x] = rand();
    }
    else{
        int t = v > x;
        insert(son[x][t],v);
        if(p[son[x][t]] < p[x])
            rotate(x,t);
    }
    update(x);
}
void erase(int &x,int v){
    if(x == v){
        if(!son[x][0] && !son[x][1]){
            x = 0;return;
        }
        int t = p[son[x][0]] > p[son[x][1]];
        rotate(x,t);
        erase(x,v);
    }
    else{
        erase(son[x][v > x],v);
    }
    update(x);
}
int grank(int r,int v){
    int x = r,ans = 0;
    while(x){
        if(v < x)
            x = son[x][0];
        else if(v == x)
            ans += siz[son[x][0]],x = 0;
        else
            ans += siz[son[x][0]]+1,x = son[x][1]; 
    }
    return ans;
}
void __print(int x,int dep){
    if(dep == 0)
        printf("%d:-------------------\n",x);
    if(x == 0) return;
    __print(son[x][0],dep+1);
    for(int i = 0;i<dep;i++) putchar(' ');
    printf("v:%d p:%d siz:%d son:%d %d\n",x,p[x],siz[x],son[x][0],son[x][1]);
    __print(son[x][1],dep+1);
    if(dep == 0)
        printf("---------------------\n");
}
bool check(int num,int l,int r){
    return 2*(grank(root[num],r+1)-grank(root[num],l)) > r-l+1;
}
void update(int pos,int last,int now){
    erase(root[last],pos);
    insert(root[now],pos);
}
void init(int *a){
    p[0] = 2147483647;
    for(int i = 1;i<=n;i++)
        insert(root[a[i]],i);
}
}

//线段树
namespace seg_tree{
#define lson (nown<<1)
#define rson ((nown<<1)|1)
#define mid ((l+r)>>1)
#define pp pair<int,int>
#define fr first
#define sc second
pp tree[MAXN<<2];
pp merge(pp a,pp b){
    pp ans;
    if(a.fr == b.fr)
        ans.fr = a.fr,ans.sc = a.sc + b.sc;
    else{
        ans.fr = a.sc > b.sc?a.fr:b.fr;
        ans.sc = a.sc - b.sc;
        if(ans.sc < 0) ans.sc *= -1;
    }
    return ans;
}
void update(int nown){
    tree[nown] = merge(tree[lson],tree[rson]);
}
void build(int nown,int l,int r,int *a){
    if(l == r){
        tree[nown] = make_pair(a[l],1);
        return;
    }
    build(lson,l,mid,a);
    build(rson,mid+1,r,a);
    update(nown);
}
pp query(int nown,int l,int r,int ql,int qr){
    if(ql <= l && r <= qr)
        return tree[nown];
    else{
        pp ans;
        if(ql <= mid && mid+1 <= qr)
            ans = merge(query(lson,l,mid,ql,qr),query(rson,mid+1,r,ql,qr));              
        else if(ql <= mid)
            ans = query(lson,l,mid,ql,qr);
        else if(mid+1 <= qr)
            ans = query(rson,mid+1,r,ql,qr);
        return ans;
    }
}
void update(int nown,int l,int r,int pos,int val){
    if(l == r)
        tree[nown] = make_pair(val,1);
    else{
        if(pos<=mid)
            update(lson,l,mid,pos,val);
        if(pos>=mid+1)
            update(rson,mid+1,r,pos,val);
        update(nown);
    }
}
}

void init(){
    read(n),read(m);
    for(int i = 1;i<=n;i++)
        read(num[i]);
    seg_tree::build(1,1,n,num);
    Treap::init(num);
}

void solve(){
    int l,r,s,k,t,win;
    for(int i = 1;i<=m;i++){
        read(l),read(r),read(s),read(k);
        win = seg_tree::query(1,1,n,l,r).first;
        win = Treap::check(win,l,r)? win:s;
        for(int i = 1;i<=k;i++){
            read(t);
            Treap::update(t,num[t],win);
            seg_tree::update(1,1,n,t,win);
            num[t] = win;
        }
        print(win),print('\n');
    }
    win = seg_tree::query(1,1,n,1,n).first;
    win = Treap::check(win,1,n)?win:-1;
    print(win),print('\n');
}

int main(){
    init();
    solve();
    flush();
    return 0;
}
cqqqwq
WRITTEN BY
cqqqwq
A student in Software Engineering.

See Also

Comments