感谢@似水流年 翻译!

题意:

给你n个数字

你需要算出它们排序后,有多少个数字>=前面所有数之和

注意:

1 1 1 1 1中,前面两个1是成立的(sum=0/1),后面三个是不成立的(sum=2/3/4)

另外会有M次修改,求修改前和每次修改后的答案

解法:

treap直接上

当然这treap需要记录father了...

insert_node:没区别

delete_node:注意要支持删从某点到根的

rotate:注意sum和father的更改

关键是那个dfs函数,求出某个地方的find_max看是否可行,如果可能有个数大于它们的全部我们就去试试找解

反正解也不多最多大概40~50个吧..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[100005];
struct node
{
    long long val;
    int weight;
    long long sum;
    int size;
    node * father;
    node * ch[2];
};
node * null;
node * root;
node * b[100005];
node * new_node(long long x)
{
    static node a[100005];
    static int top=0;
    node * t=&a[top++];
    t->val=x;
    t->sum=x;
    t->weight=rand();
    t->size=1;
    t->father=null;
    t->ch[0]=null;
    t->ch[1]=null;
    return t;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->sum=x->sum;
    y->size=x->size;
    y->father=x->father;
    x->sum=x->ch[0]->sum+x->ch[1]->sum+x->val;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x->father=y;
    x=y;
}
void insert_node(node * &x,node * y)
{
    if (x==null)
    {
        x=y;
        return;
    }
    x->size++;
    x->sum+=y->sum;
    int c;
    if (y->val>x->val)
    {
        c=1;
    }
    else
    {
        c=0;
    }
    y->father=x;
    insert_node(x->ch[c],y);
    if (x->ch[c]->weight>x->weight) rotate(x,c);
}
void delete_node(node * &x,long long y)
{
    x->size--;
    x->sum-=y;
    if (x->val==y)
    {
        int c;
        if (x->ch[0]->weight>x->ch[1]->weight)
        {
            c=0;
        }
        else
        {
            c=1;
        }
        if (x->ch[c]==null)
        {
            x=null;
            return;
        }
        rotate(x,c);
        delete_node(x->ch[!c],y);
    }
    else
    {
        if (x->val<y)
        {
            delete_node(x->ch[1],y);
        }
        else
        {
            delete_node(x->ch[0],y);
        }
    }
}
int n;
long long max_val(node * x)
{
    if (x->ch[1]==null) return x->val;
    return max_val(x->ch[1]);
}
int dfs(node * x,long long y)
{
    int sum=0;
    if (x->ch[0]!=null)
    {
        if (max_val(x->ch[0])>=y)
        {
            sum+=dfs(x->ch[0],y);
        }
    }
    if (x->val>=y+x->ch[0]->sum)
    {
        sum++;
    }
    if (x->ch[1]!=null)
    {
        if (max_val(x->ch[1])<y+x->ch[0]->sum+x->val) return sum;
        sum+=dfs(x->ch[1],y+x->ch[0]->sum+x->val);
    }
    return sum;
}
int query()
{
    return dfs(root,0);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    cin>>n;
    int i;
    null=new_node(0);
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    null->weight=-1;
    null->size=0;
    root=null;
    for (i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=new_node(a[i]);
        insert_node(root,b[i]);
    }
    printf("%d\n",query());
    int m;
    cin>>m;
    for (i=0;i<m;i++)
    {
        int x;
        long long y;
        cin>>x>>y;
        x--;
        node * t=b[x]->father;
        for (;t!=null;)
        {
            t->size--;
            t->sum-=b[x]->val;
            t=t->father;
        }
        if (b[x]==root)
        {
            delete_node(root,b[x]->val);
        }
        else
        {
            int c;
            if (b[x]->father->ch[0]==b[x]) c=0; else c=1;
            delete_node(b[x]->father->ch[c],b[x]->val);
        }
        b[x]->val=y;
        b[x]->sum=y;
        b[x]->size=1;
        b[x]->ch[0]=null;
        b[x]->ch[1]=null;
        b[x]->father=null;
        insert_node(root,b[x]);
        printf("%d\n",query());
    }
    return 0;
}