首页 > 代码库 > NBUT 1457 Sona (莫队算法)
NBUT 1457 Sona (莫队算法)
题目大意:
求一段区间内 出现的数字的次数的三次方的和
思路分析:
这要水过去的题目真是难,各种优化。
不能用map , 要离散化之后 先处理lowerbound。优化输入。。。
时间卡的很紧。。
题目直接用莫队水过去。
如果你超时的话,不妨试试上面三种优化。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <map> #include <cmath> #define maxn 100005 using namespace std; typedef long long LL; int app[maxn]; int pos[maxn]; int save[maxn]; int x[maxn]; map<int,int>mymap; struct foo { int l,r,index; LL ans; bool operator < (const foo &cmp) const { if(pos[l]==pos[cmp.l])return r<cmp.r; return pos[l]<pos[cmp.l]; } }Q[maxn]; int n; inline void scanf_(int &num){ char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-'){ neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; } bool cmp_id(const foo &a,const foo &b) { return a.index<b.index; } int sz; void modify(int p,LL &ans,int add) { ans-=(LL)app[x[p]]*app[x[p]]*app[x[p]]; app[x[p]]+=add; ans+=(LL)app[x[p]]*app[x[p]]*app[x[p]]; } int main() { while(scanf("%d",&n)!=EOF) { memset(app,0,sizeof app); int SIZE = (int)sqrt(n*1.0); for(int i=1;i<=n;i++) { scanf_(save[i]); x[i]=save[i]; pos[i]=(i-1)/SIZE+1; } int m; scanf_(m); for(int i=0;i<m;i++) { scanf_(Q[i].l); scanf_(Q[i].r); Q[i].index=i; } sort(save+1,save+n+1); sz=unique(save+1,save+n+1)-save; for(int i=1;i<=n;i++) { x[i] = lower_bound(save+1,save+sz,x[i])-save; } sort(Q,Q+m); LL ans=0; for(int i=0,l=1,r=0;i<m;i++) { if(r<Q[i].r) { for(r=r+1;r<=Q[i].r;r++) modify(r,ans,1); r--; } if(r>Q[i].r) { for(;r>Q[i].r;r--) { modify(r,ans,-1); } } if(l<Q[i].l) { for(;l<Q[i].l;l++) modify(l,ans,-1); } if(l>Q[i].l) { for(l=l-1;l>=Q[i].l;l--) modify(l,ans,1); l++; } if(Q[i].l==Q[i].r) { Q[i].ans=1; continue; } Q[i].ans=ans; } sort(Q,Q+m,cmp_id); for(int i=0;i<m;i++) printf("%I64d\n",Q[i].ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。