主席书写炸了

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,len[100010],cnt,maxn;
struct node{
    int lson,rson,sum,weight;
}tree[2000010];
struct gold{
    int w,v;
}a[100010],b[100010];
bool cmp(gold x,gold y){
    return ((double)(x.v)/x.w)>((double)(y.v)/y.w);
}
int build(int l,int r){
    int x=++cnt,mid=(l+r)/2;
    if(l<r){
        tree[x].lson=build(l,mid);
        tree[x].rson=build(mid+1,r);
    }
    return x;
}
int upt(int x,int l,int r,int p,gold g){
    int k=++cnt,mid=(l+r)/2;
    tree[k].lson=tree[x].lson;
    tree[k].rson=tree[x].rson;
    tree[k].sum=tree[x].sum+g.v;
    tree[k].weight=tree[x].weight+g.w;
    if(l<r){
        if(p<=mid) tree[k].lson=upt(tree[x].lson,l,mid,p,g);
        else tree[k].rson=upt(tree[x].rson,mid+1,r,p,g);
    }
    return k;
}
double query(int u,int v,int l,int r,int ls,int rs){
    int wi=tree[v].weight-tree[u].weight,vi=tree[v].sum-tree[u].sum,mid=(l+r)/2; 
    if(l>r||!maxn||!wi) return 0;
    if(l==r){
        if(maxn>=wi){
            maxn-=wi;
            return vi;
        } 
        else return (double)vi*((double)maxn/wi);
    }
    if(l<=ls&&r>=rs&&maxn>=wi){
        maxn-=wi;
        printf("%d %d\n",wi,vi);
        return vi;
    }
    return query(tree[u].lson,tree[v].lson,l,mid,ls,rs)+query(tree[u].rson,tree[v].rson,mid+1,r,ls,rs);
}
map<double,int> ma;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].v),b[i].v=a[i].v;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].w),b[i].w=a[i].w;
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) ma.insert(make_pair((double)b[i].v/b[i].w,i));
    len[0]=build(1,n);
    for(int i=1;i<=n;i++){
        map<double,int>::iterator x=ma.find((double)a[i].v/a[i].w);
        len[i]=upt(len[i-1],1,n,x->second,b[x->second]);
//      print(1,1,n);
//      printf("\n");
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&l,&r,&maxn);
        double ans=query(len[l-1],len[r],1,n,l,r);
        ans+=1e-3;
        if(i!=m) printf("%.2lf ",ans);
        else printf("%.2lf",ans);
    }
}

哪位大佬帮忙调一下

0 条评论

目前还没有评论...

信息

ID
1678
难度
9
分类
数据结构 | 线段树 点击显示
标签
递交数
1675
已通过
16
通过率
1%
被复制
4
上传者