CodeForces 85D Sum of Medians(treap)

题意:维护一个序列,支持不带优先级加入和删除操作,然后强制在线询问下标$mod 5=3$的数之和。

插入和删除都可以考虑用$treap$维护,然后对于求和操作,最拿衣服的想法就是枚举每个小于总size的下标,然后对$treap$进行$k~th$操作,记下和。这样期望是$\mathcal O(\frac{n^2}{5}logn)$的样子,对于$n=1e5$的数据还是跑不过去的。于是考虑直接$O(1)$查询答案…对于treap的每个节点记下$4$个$sum$,分别表示该子树下标$mod 5$的结点之和。更新时通过左右结点更新即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int v,r,siz;
node* ch[2];
ll sum[5];
void maintain()
{
int pre=0;
int s=1;
if(ch[0]!=NULL) s+=ch[0]->siz;
pre=s;
if(ch[1]!=NULL) s+=ch[1]->siz;
siz=s;
memset(sum,0,sizeof(sum));
sum[(pre%5)]=v;
for(int i=0;i<5;i++){
if(ch[0]!=NULL) sum[i]+=ch[0]->sum[i];
if(ch[1]!=NULL) sum[(pre+i)%5]+=ch[1]->sum[i];
}
}
node(int x){
this->v=x;
this->r=rand();
this->siz=1;
this->ch[0]=this->ch[1]=NULL;
memset(sum,0,sizeof(sum));
this->sum[1]=x;
}
int cmp(int x){
if(x==v) return -1;
return x<v?0:1;
}
};
node* rt;
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void Insert(node* &o,int v)
{
if(o==NULL) {o=new node(v);return;}
else{
int d=v<o->v?0:1;
Insert(o->ch[d],v);
if(o->ch[d]->r>o->r) rotate(o,d^1);
if(o!=NULL) o->maintain();
}
}
void Remove(node* &o,int v)
{
int d=o->cmp(v);
if(d==-1){
if(o->ch[0]!=NULL && o->ch[1]!=NULL){
int d2=o->ch[0]->r>o->ch[1]->r?1:0;
rotate(o,d2);
Remove(o->ch[d2],v);
if(o!=NULL) o->maintain();
}
else if(o->ch[0]!=NULL) o=o->ch[0];
else o=o->ch[1];
}else{
Remove(o->ch[d],v);
if(o!=NULL) o->maintain();
}
}
int kth(node* &o,int k)
{
if(k==0 || o==NULL || o->siz<k) return -1;
else{
int s=o->ch[0]==NULL?0:o->ch[0]->siz;
if(k==s+1) return o->v;
else if(k<=s) return kth(o->ch[0],k);
else return kth(o->ch[1],k-s-1);
}
}
void print(node* &o)
{
if(o==NULL) return;
if(o->ch[0]!=NULL) print(o->ch[0]);
printf("v=%d r=%d siz=%d || ",o->v,o->r,o->siz);
if(o->ch[1]!=NULL) print(o->ch[1]);
}
string Coms[]={"add","del","sum"};
int n;
int main()
{
scanf("%d",&n);
string com;
int x;
for(int i=0;i<n;i++)
{
cin>>com;
if(com==Coms[0]){
scanf("%d",&x);
Insert(rt,x);
}else if(com==Coms[1]){
scanf("%d",&x);
Remove(rt,x);
}else{
if(rt==NULL) printf("0\n");
else{
printf("%lld\n",rt->sum[3]);
}
}
}
return 0;
}

然后其实这题…$vector$模拟就可以水过去

这个像擦边球一样…插入和删除单次$logn$,然后查询因为是最坏$\frac{n^2}{5}$,所以就卡$3~secs$跑过去了…

行吧

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> vec;
int n;
string Coms[]={"add","del","sum"};
bool flag=true;
int main()
{
scanf("%d",&n);
string com;
int k;
ll ans=0;
for(int i=0;i<n;i++)
{
cin>>com;
if(com==Coms[0]){
scanf("%d",&k);flag=false;
vec.insert(lower_bound(vec.begin(),vec.end(),k),k);
}else if(com==Coms[1]){
scanf("%d",&k);flag=false;
vec.erase(lower_bound(vec.begin(),vec.end(),k));
}else{
ans=0;
for(int j=2;j<(int)vec.size();j+=5)
ans+=vec[j];
printf("%lld\n",ans);
}
}
return 0;
}