P4587 [FJOI2016]神秘数 题解
PosVII
·
·
题解
前言
考场上想的 O(n\sqrt{n}\log n) 做法，因为不太会分块，所以代码比较难看。但是调整块长后变最优解第二，说明常数挺小。
思路
------------
不难想就是一个使 $ans = 0$，然后进行很多次 $ans = \Sigma_{i=l}^{r}[a_{i} \leq ans+1] \times a_{i}$ 直到 $ans$ 不变，发现第 $i$ 次操作过后如果没有结束则 $2^i-1 \leq ans$，也就是说最多执行 $\log v$ 次操作。每次询问暴力来做还是 $O(n)$ 的，考虑对数据离散化后分块，每个整块维护数值大小在其块内的前缀和，散块需要用 vector 存储每个数值在数组中出现的下标然后二分查找出现次数。
$O(n\sqrt{n}\log n)$ 做法
------------
发现这些询问都是连续的，考虑一次询问解决，其实就是使询问的右端点一直变直到结束，不难发现约等于询问一次，还是 $O(\sqrt{n}\log n)$ 的。
**code**
------------
```
#include<bits/stdc++.h>
using namespace std;
template<typename G> inline void read(G &x) {x=0;G f=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') {x=x*10+(ch^48);ch=getchar();}x*=f;}
template<typename G> inline void write(G x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int MAXN=1e5+5,MAXM=405;
struct node{
int l,r,idx;
}q[MAXN];
bool cmp(node x,node y) {
return x.r<y.r;
}
int sum[MAXM],opt[MAXN],lst,ans,d[MAXM][MAXN];
int sqn,b[MAXN],pos[MAXN];
int n,m,a[MAXN],l,r,now,le[MAXM],ri[MAXM],tot;
vector<int> v[MAXN];
signed main() {
read(n);
for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b-1;sqn=sqrt(n);le[1]=1;
for(int i=2;i<=cnt;++i) {
if(!le[(i+sqn-1)/sqn]) le[(i+sqn-1)/sqn]=i;
ri[(i+sqn-1)/sqn]=i;
}
tot=(cnt+sqn-1)/sqn;
for(int i=1;i<=n;++i) {
a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
d[(a[i]+sqn-1)/sqn][i]=b[a[i]];
for(int j=1;j<=tot;++j) d[j][i]+=d[j][i-1];
}
read(m);
for(int i=1;i<=m;++i) {
read(q[i].l),read(q[i].r),q[i].idx=i;
}
sort(q+1,q+1+m,cmp);int las=1;
for(int i=1;i<=m;++i) {
for(int j=las;j<=q[i].r;++j) {
v[a[j]].emplace_back(j);
}
las=q[i].r+1;ans=0,now=1,lst=0;
while(now<=tot) {
if(b[ri[now]]<=ans+1) {
ans+=d[now][q[i].r]-d[now][q[i].l-1];
++now;
continue;
}
lst=0;
for(int j=le[now];j<=ri[now];++j) {
if(b[j]>ans+1) goto end;
if(b[ri[now]]<=ans+1) {
ans+=d[now][q[i].r]-d[now][q[i].l-1]-lst;
break;
}
int k=v[j].end()-lower_bound(v[j].begin(),v[j].end(),q[i].l);
ans+=k*b[j];
lst+=k*b[j];
}
++now;
}
end:;
opt[q[i].idx]=ans+1;
}
for(int i=1;i<=m;++i) write(opt[i]),putchar('\n');
return 0;
}
```