hdu4288 Coder（线段树+离散化）

81 阅读 0 评论 54 点赞

我是靠谱客的博主开朗小松鼠，最近开发中收集的这篇文章主要介绍hdu4288 Coder（线段树+离散化），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

huangjing

题意：

题目中给了三个操作

1：add x 就是把x插进去

2：delete x 就是把x删除

3：sum 就是求下标%5=3的元素的和。

还有一个条件是插入和删除最后都要保证数列有序。。。

首先告诉一种暴力的写法。。因为时间非常充足，需要对stl里面的函数有所了解。。

就是直接申明一个vector的容器，然后直接用vector里面的操作比如 insert，erase等等操作。。不过这个效率很低。。

最后跑出来6000多ms。。（强哥的代码）

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
char s[5];
int n;
vector<int>a;
int main()
{
int len,val;
vector<int>::iterator iter;
while(cin>>n)
{
len=0;
a.clear();
while(n--)
{
scanf("%s",s);
if(s[0]=='s')
{
long long ans = 0;
for(int i=2; i < len ; i+=5)
ans += a[i];
cout<<ans<<endl;
}
else if(s[0]=='a')
{
len++;
scanf("%d",&val);
iter=lower_bound(a.begin(),a.end(),val);
a.insert(iter,val);
}
else
{
len--;
scanf("%d",&val);
iter= lower_bound(a.begin(),a.end(),val);
a.erase(iter); // basic coding
}
}
}
return 0;
}

第二种方法是线段树做法，这个要维护5颗线段树，结构体里面保存每个节点的个数，首先因为线段树不支持插入，删除，要维护一个个数cnt，当插入一个数的时候，你看原来%3的数，现在取余肯定等于2，那么怎么办呢？？那么这个cnt就起到了神奇的作用，每当插入删除的时候就把相应的节点数变化，来维护那5棵线段树。。最后因为没有告诉数据范围，所以要采取离散化，然后离线处理，最后得出所有要操作的总个数，然后依此建树，第一次用离散化，觉得好高大上。。。

代码：（参考自cxlove）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100000+10;
int n,a[maxn],b[maxn];
char op[maxn][5];
struct Tree
{
int cnt;
ll sum[5];
}tree[maxn<<2];
void buildtree(int l,int r,int dex)
{
tree[dex].cnt=0;
memset(tree[dex].sum,0,sizeof(tree[dex].sum));
if(l==r)
return;
int mid=(l+r)>>1;
buildtree(l,mid,dex<<1);
buildtree(mid+1,r,dex<<1|1);
}
void push_up(int dex)
{
for(int i=0;i<5;i++)
tree[dex].sum[i]=tree[dex<<1].sum[i]+tree[dex<<1|1].sum[((i-tree[dex<<1].cnt)%5+5)%5];
}
void update(int l,int r,int dex,int pos,int flag,int val)
{
tree[dex].cnt+=flag;
if(l==r)
{
if(flag==1)
tree[dex].sum[1]=val;
else
tree[dex].sum[1]=0;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
update(l,mid,dex<<1,pos,flag,val);
else update(mid+1,r,dex<<1|1,pos,flag,val);
push_up(dex);
}
int main()
{
int tot,pos,flag;
while(~scanf("%d",&n))
{
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%s",op[i]);
if(op[i][0]!='s')
{
scanf("%d",&b[i]);
a[tot++]=b[i];
}
}
sort(a,a+tot);
tot=unique(a,a+tot)-a;
if(tot==0)
memset(tree[1].sum,0,sizeof(tree[1].sum));
else buildtree(1,tot,1);
for(int i=1;i<=n;i++)
{
pos=lower_bound(a,a+tot,b[i])-a;
pos++;
if(op[i][0]=='a')
{
flag=1;
update(1,tot,1,pos,flag,b[i]);
}
else if(op[i][0]=='d')
{
flag=-1;
update(1,tot,1,pos,flag,b[i]);
}
else
printf("%I64dn",tree[1].sum[3]);
}
}
return 0;
}