Codeforces 85 D. Sum of Medians

时间:2022-04-08 12:16:49

题目链接:http://codeforces.com/contest/85/problem/D


做法果然男默女泪啊.....

大概就是直接开了一个$vector$每次插入删除都用自带的$insert$和$erase$,然后查询也是暴力搞。

那么为啥么过得很有理有据呢?

  1.首先考虑如果没有修改我就能继承上一次的答案...

  2.修改我们假设(就是)${O(logn)}$的。

  3.每次暴力查询是$5$个数字一步。

  4.显然一开始并不是上来就有${100000}$个数字

所以大概复杂度会是${O(n^{2}/40)}$的....


 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10010
#define llg int
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,w,x;
vector<llg>a;
long long ans;
bool pd;
char s[];
inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} int main()
{
yyj("sum");
cin>>n;
while (n--)
{
scanf("%s",s);
if (s[]=='s')
{
if (!pd) {printf("%lld\n",ans); continue;}
ans=;
w=a.size();
for (llg i=;i<w;i+=) ans+=a[i];
pd=false;
printf("%lld\n",ans);
}
else
{
x=getint();
if (s[]=='a') a.insert(lower_bound(a.begin(),a.end(),x),x);
else a.erase(lower_bound(a.begin(), a.end(), x));
pd=true;
}
}
return ;
}

当然正解也是可以想出来的,就是一个线段树每个点维护所有数字%5=x的数字和,然后记录右移多少。