这是今年的福建省选原题……按说不是很难但我却卡了很长时间……
我的写法十分诡异难以调试……以后得换一种写法了
题解直接抄一下懒得写了
------------------------------
这个模型还是比较常见的。对于给定序列，我们要求的是最小的x，使所有<=x的数的和比x小。
设不同权值个数为t，我们用可持久化建出t棵线段树，每棵线段树均以下标为关键字，以支持查询小于等于某一权值的数在给定区间的和为多少。
那么在区间[L, R]中，假设答案为x0。我们可在线段树中查询[L, R]区间内所有不超过x0的数的和S。假如S小于x0，x0就是答案；否则答案一定至少为S + 1。迭代即可。
复杂度O(nlogn + kmlogn)，k为迭代次数，不超过45（最坏情况由斐波那契数列卡到）
------------------------------
我真的是严格按照这个题解写的！但是其他人的写法都和题解不一样……所以我很诧异……UPD:其实是一样的！只是细节有点区别！我真是太弱了！
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,siz,a[100005],b[100005],root[100005],bn,m;
vector<int> V[100005];
struct SegTree{
int nl,nr,l,r,sum,cre;
}tree[4000005];
void Add(int &rt,int lastrt,int l,int r,int pos,int val,int Rev){
if(Rev!=tree[rt].cre){rt=++siz;tree[rt].nl=tree[lastrt].nl;tree[rt].nr=tree[lastrt].nr;tree[rt].l=l;tree[rt].r=r;tree[rt].cre=Rev;}
if(l==r){tree[rt].sum+=val;return;}
int mid=l+r>>1;
if(pos<=mid)Add(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val,Rev);
if(pos>mid)Add(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val,Rev);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}
int Sum(int rt,int l,int r){
if(rt==0)return 0;
if(l<=tree[rt].l && tree[rt].r<=r){
return tree[rt].sum;
}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(tree[rt].nl,l,r);
if(r>mid)ans+=Sum(tree[rt].nr,l,r);
return ans;
}
int main(){
freopen("4408.in","r",stdin);
freopen("4408.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}
sort(b+1,b+n+1);
bn=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+bn+1,a[i])-b;V[a[i]].push_back(i);}
for(int i=1;i<=bn;i++){for(int j=0;j<V[i].size();j++)Add(root[i],root[i-1],1,n,V[i][j],b[a[V[i][j]]],i);}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d %d",&l,&r);
int ans=0,tmp=-1;
while(tmp<=ans){
tmp=ans+1;
ans=Sum(root[upper_bound(b+1,b+bn+1,tmp)-b-1],l,r);
}
printf("%d\n",ans+1);
}
return 0;
}
评论 (0)
