【LOJ】#2174. 「FJOI2016」神秘数

时间:2022-08-30 15:18:43

题解

这道题的结论很显然= =

就是暴力求的话,把一个区间的数排一下序,如果当前这个数大于前面所有数的前缀和+1,那么前缀和+1即我们所求的答案

那么我们设置一个当前答案(初始为1),在主席树上求出来小于这个答案的数的和是多少,设为t,如果t < ans,那么答案就是ans,如果t >= ans,那么设置ans = t + 1

容易发现,在两次操作之后ans必然翻倍,所以复杂度是\(O(M \log N \log \sum a_{i})\)

代码

#include <bits/stdc++.h>
#define MAXN 100005
//#define ivorysi
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int sum;
int lc,rc;
}tr[MAXN * 40];
int Ncnt,rt[MAXN];
int N,a[MAXN],M,MK;
void Insert(const int &x,int &y,int L,int R,int v) {
y = ++Ncnt;
tr[y] = tr[x];
tr[y].sum += v;
if(L == R) return;
int mid = (L + R) >> 1;
if(v <= mid) Insert(tr[x].lc,tr[y].lc,L,mid,v);
else Insert(tr[x].rc,tr[y].rc,mid + 1,R,v);
}
void Init() {
read(N);
for(int i = 1 ; i <= N ; ++i) read(a[i]),MK = max(MK,a[i]);
read(M);
for(int i = 1 ; i <= N ; ++i) {
Insert(rt[i - 1],rt[i],1,MK,a[i]);
}
}
int query(int L,int R,int v) {
L = rt[L - 1],R = rt[R];
int l = 1,r = MK,res = 0;
while(1) {
if(l == r) {res += tr[R].sum - tr[L].sum;break;}
int mid = (l + r) >> 1;
if(v <= mid) {
r = mid;
L = tr[L].lc;R = tr[R].lc;
}
else {
l = mid + 1;
res += tr[tr[R].lc].sum - tr[tr[L].lc].sum;
L = tr[L].rc;R = tr[R].rc;
}
}
return res;
}
void Solve() {
Init();
int L,R;
while(M--) {
read(L);read(R);
int ans = 1;
while(1) {
int t = query(L,R,ans);
if(t >= ans) ans = t + 1;
else break;
}
out(ans);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}