大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
主题链接:
题意:
。。
。由于时间很充足,须要对stl里面的函数有所了解。
。
。只是这个效率非常低。。
。(强哥的代码)
#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; }
。
最后由于没有告诉数据范围,所以要採取离散化,然后离线处理,最后得出全部要操作的总个数,然后依此建树。第一次用离散化,认为好高大上。。。
#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("%I64d\n",tree[1].sum[3]); } } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117629.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...