priority_queue和multiset异同以及线段树空树插入维护初见

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
const int M = 2e5 + 7 ;
int Q, n, m, w[M];
ll sum;
int k;
priority_queue<int,vector<int>,greater<int>> pre;
priority_queue<int,vector<int>,less<int>> q;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>Q;
    while(Q--){
        /* init */
        sum = 0;k=0;
        while(!q.empty()) q.pop();
        while(!pre.empty()) pre.pop();
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=1;i<=n;i++){
            /* 根据题意不能弹出本次加入的 */
            /* 根据题意应该不会在空的时候满足条件 */
            // int pre=inf;
            /*每弹出一个k++,所以每回收pre一个k--*/
            // while(!pre.empty()) pre.pop();
            while(!q.empty()&&sum+w[i]>m){
                k++;
                pre.push(q.top());
                sum-=q.top();
                q.pop();
            }
            /*输出*/
            cout<<k<<" ";
            if(i==n){ cout<<endl; break; }
            /*回溯*/
            ll tmp = 0;
            /* = 再想想*/
            bool f=0;
            while(!pre.empty()&&tmp+pre.top()<=w[i]){
                f=1;
                tmp += pre.top();
                q.push(pre.top());
                k--;
                pre.pop();
            }
            /*能加入一个就无需加本身了,要加回之前的sum值
            本身未加入的话就相当于弹出了一个k++*/
            /*不对,加回本身,让其在后面的循环中进入pre*/
            // if(f) sum += tmp,k++;
            if(f) sum += tmp;
            q.push(w[i]);
            sum += w[i];
        }
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<iostream>
#include<set>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
multiset<int> ss;

int main(){
    int t;
    scanf("%d", &t);
    while (t--) {
        ss.clear();
        long long int n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        long long int sum = 0;
        int tem = 0;
        for (int i = 0; i < n; i++) {
            long long int suma = sum;
            int jishu = 0;
            if (suma + a[i] > m) {
                auto j = ss.end();
                /* 这里用计数jishu记下软删除的数量，由于priority_queue
                只能访问第一个值，所以不支持软硬删除操作...所以会用真实删除再
                恢复的操作会TLE...因为这样会从O(nlog(n))魔化到O(n^2) */
                /* 由题意a[i]<=m，满足下面条件时一定不会出现ss为空 */
                while (suma + a[i] > m) {
                    j--;
                    suma -= *j;
                    jishu++;
                }
            }
            /* 第一个铁定是0的 */
            printf("%d ", jishu + tem);
            ss.insert(a[i]);
            auto j = ss.end();
            sum += a[i];
            /* 用tem记录下硬删除的数量 */
            while (sum > m) {
                j--;
                sum -= *j;
                /* 这里由于find返回的是指针，所以就会只删除一个值
                而不是删除数值那样把所有数值都删除掉 */
                ss.erase(ss.find(*j));
                tem++;
            }
        }
        printf("\n");
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include<bits/stdc++.h>
using namespace std;
#define mod 1e9+7
#define ll long long
const int M = 2e5+7;
ll int a[M],number[M<<2],bz[M<<2];
int number2[M<<2],bz2[M<<2],to[M];
struct node{
    int id;
    ll b;
} no[M];

bool cmp(node a,node b){
    return a.b==b.b ? a.id<b.id : a.b<b.b;
}

/* 自己重写std感觉上推数值好像还是不对，如果不理解的话，下次就算有板子也不能秒掉！
所以还是要先理解一下 ，多多重现算法*/
/* 先写着，等下写完全部看看有没有新的认识 */
/* 2019年7月30日16:59:35 还是不懂，维护区间之和难道不是要左右相加吗？

2019年7月30日20:34:57 突然灵光一闪！
因为你一开始是一棵空树，然后你一个个插入，如果使用的是max，就相当于(to[i],n+1)这个区间以及每个子区间
都是你的插入值的和.         因为都是直接到了叶子节点去加和

如果使用加法，那么就出错了，就有很多重复计算，所以说[1->n]区间就是最大的前缀和

所以询问的时候就可以直接加和*/
void PushUp(int rt){
    number[rt] = max(number[rt<<1],number[rt<<1|1]);
}

/* 其实这里是多组测试的初始化0值 */
/* 但是number2不PushUp清零吗？这里好像有问题，但为什么std能AC
惊呆的发现竟然放在了pushdown下推标记的时候清零了...感觉线段树的写法真多*/
void build(int l,int r,int rt){
    bz[rt]=bz2[rt]=number[rt]=0;
    if(l==r){number2[rt]=0;return;}
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    PushUp(rt);
}

void pushdown(int l,int r,int rt){
    if(bz[rt]){
        bz[rt<<1] += bz[rt];
        bz[rt<<1|1] += bz[rt];
        number[rt<<1] += bz[rt];
        number[rt<<1|1] += bz[rt];
        bz[rt] = 0;
    }
    if(bz2[rt]){
        bz2[rt<<1] += bz2[rt];
        bz2[rt<<1|1] += bz2[rt];
        number2[rt<<1] += bz2[rt];
        number2[rt<<1|1] += bz2[rt];
        bz2[rt] = 0;
    }
}

void change(ll o,int L,int R,int l,int r,int rt){
    if(L>R) return;
    if(l==r){
        number[rt]+=o;
        /* 之前初始化成了0，所以这里可以这样...这个标程写得真随意... */
        number2[rt]+=1;
        return ;
    }
    /* 此节点(区段l,r)全被包含在内 */
    if(L<=l && r<=R){
        /* 先自己赋值，下推标记就直接给儿子赋值 */
        number[rt]+=o;
        bz[rt]+=o;
        bz2[rt] += 1;
        return ;
    }
    int mid = (l+r)>>1;
    /* pushdown和PushUp都只管修改相邻层 */
    pushdown(l,r,rt);
    /* 区段l,r包含L,R,或者有交叠,则访问子节点(子区段) */
    if(L<=mid) change(o,L,R,l,mid,rt<<1);
    if(R>mid) change(o,L,R,mid+1,r,rt<<1|1);
    PushUp(rt);
}

ll query(ll k,int l,int r,int rt){
    if(l==r) return number2[rt];
    int mid = (l+r)>>1;
    pushdown(l,r,rt);
    int ans;
    if(k < number[rt<<1]) ans = query(k,l,mid,rt<<1);
    else ans = query(k,mid+1,r,rt<<1|1);
    PushUp(rt);
    return ans;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,n+1,1);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            no[i].b = a[i];
            no[i].id = i;
        }
        sort(no+1,no+n+1,cmp);
        /* 把与n+1有关的节点都打上number=1e9,number2=1的标记...
        只给n+1对应的叶子节点处打上了标记！其他地方没有进去过！
        就相当于在那里插入了一点*/
        change(1e9,n+1,n+1,1,n+1,1);
        for(int i=1;i<=n;i++) to[no[i].id] = i;
        for(int i=1;i<=n;i++){
            /*一个个插入,第一个时还没插入，是空树，所以肯定返回0*/
            ll k = query(m-a[i],1,n+1,1);
            printf("%lld ",i-k);
            /*按照队友的说法,那这里就是插入第一个*/
            /* 给排名在to[i]到n+1的地方都所有区段打上区间数值和number
            和此区间个数和number2 */
            change(a[i],to[i],n+1,1,n+1,1);
        }
        puts("");
    }
    return 0;
}