Znzryb's Blog
0%

Posted on Edited on

思路讲解

参考题解

https://www.luogu.com.cn/article/1o6edp6y

zkw线段树写法

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
// 参考了（抄了）beta99999 的提交  https://www.luogu.com.cn/record/216441078
// 因为自己重写的，目前只支持zkw线段树，配置上只保留了identity
// 采用0-based，左开右闭区间，注意这个区间转化
// AC https://www.luogu.com.cn/record/230419677 最大子段和
template <typename T,typename value_type> struct base_segtree{
    int n,sz;
    vector<value_type> tr;
    static int bit_ceil(int x){int res=1;while(res<x){res<<=1;} return res;};
    // zkw线段树开两倍大小，identity为默认值
    base_segtree(int n):n(n),sz(bit_ceil(n)),tr((sz<<1),T::identity){}    
    T *derived() { return static_cast<T*>(this); }
    void pushup(int o){
        tr[o]=T::op(tr[o<<1],tr[o<<1|1]);
    }

    // zkw选配  
    int dis(int o){return __lg(sz)-__lg(o);}    // 倒数第几层？有倒数第0层
    int len(int o){return 1<<dis(o);}   // （直接调用就可以，就是左闭右开区间长度）
    int le(int o){return (o<<dis(o))-sz; }  // 左闭
    int rr(int o){return (o+1<<dis(o))-sz;} // 右开
    void build(){
        for(int o=sz-1;o>=1;--o){
            derived()->pushup(o);
        }
    }
    template<typename D> 
    void update(int l,D x){
        tr[l+sz]=x;
        int o=l+sz;
        for(int i=1;i<=__lg(o);++i){
            derived()->pushup(o>>i);
        }
    }
    value_type query(int l, int r){
        l+=sz;r+=sz;    // T:: 调用的是类的静态成员，无需实例化
        value_type resl=T::identity,resr=T::identity;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) resl=T::op(resl,tr[l++]);
            if(r&1) resr=T::op(tr[--r],resr);
        }
        return T::op(resl,resr);
    }
    void assign(int i,value_type a){
        tr[i+sz]=a;
    }
};
struct State{
    ll pre,suf,mx,sum;
    // State(ll pre,ll suf,ll mx,ll sum):pre(pre),suf(suf),mx(mx),sum(sum) {}
};
struct segtree:base_segtree<segtree, State>{
    static constexpr State identity={-INF,-INF,-INF,0};
    static State op(const State &a,const State &b){
        return {
		        // 这个是在重新计算 A 和 B 合并以后的区间的最大前缀和。
            max(b.pre+a.sum,a.pre),
            // 这个是在重新计算 A 和 B 合并以后的区间的最大后缀和。
            max(b.suf,b.sum+a.suf),
            // 这个是在计算 A 和 B 合并以后区间的最大子段和。
            max({a.mx,b.mx,a.suf+b.pre}),
            // 这个就比较简单，这个其实就是在计算区间的和，A 和 B 合并以后的区间的和。
            a.sum+b.sum
        };
    }
    segtree(ll n):base_segtree<segtree, State>(n){}
};
constexpr State segtree::identity;

AC代码

AC

https://www.luogu.com.cn/record/199579498

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e5)+10,MIN=-1e17+9,que=MAXN-10;
ll N,M;
// P4513 小白逛公园
// https://www.luogu.com.cn/problem/P4513
struct Tree {
	int l=0,r=0;
	ll maxLeft,maxRight,sum,ans;
}tr[MAXN*4];
// 区间合并代码
inline void merge(int k) {
	int lson = k*2,rson=k*2+1;
	tr[k].sum=tr[lson].sum+tr[rson].sum;
	//                                    一定包含左端点且相连
	tr[k].maxLeft=max(tr[lson].maxLeft,tr[lson].sum+tr[rson].maxLeft);
	//                                     一定包含右端点且相连
	tr[k].maxRight=max(tr[rson].maxRight,tr[lson].maxRight+tr[rson].sum);
	//                                         相连且为最优
	tr[k].ans=max({tr[lson].ans,tr[rson].ans,tr[lson].maxRight+tr[rson].maxLeft});
}
inline Tree mergeTr(Tree lt,Tree rt) {
	Tree res;
	res.sum=lt.sum+rt.sum;
	//                                    一定包含左端点且相连
	res.maxLeft=max(lt.maxLeft,lt.sum+rt.maxLeft);
	//                                     一定包含右端点且相连
	res.maxRight=max(rt.maxRight,lt.maxRight+rt.sum);
	//                                         相连且为最优
	res.ans=max({lt.ans,rt.ans,lt.maxRight+rt.maxLeft});
	return res;
}
void buildTree(int x,int l,int r) {
	if(l==r) {
		tr[x].l=tr[x].r=l;
		tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=MIN;
		return;
	}
	tr[x].l=l,tr[x].r=r;
	tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=MIN;
	int mid=l+r>>1;
	buildTree(x*2,l,mid);
	buildTree(x*2+1,mid+1,r);
}
//           树上位置，位置，  分数
void change(int x,int pos,ll sc) {
	if(tr[x].l==pos && tr[x].r==pos) {
		tr[x].sum=tr[x].ans=tr[x].maxLeft=tr[x].maxRight=sc;
		return;
	}
	int mid=tr[x].l+tr[x].r>>1;
	// 在右子树
	if(pos>mid) change(x*2+1,pos,sc);
	else change(x*2,pos,sc);// 在左子树
	merge(x);
}
Tree query(int x,int l,int r) {
	if(l<=tr[x].l && tr[x].r<=r) {
		return tr[x];
	}
	int mid=tr[x].l+tr[x].r>>1;

	if(l>mid) {
		// 区间全部在右树
		return query(x*2+1,l,r);
	}else{
		// 区间全部在左树
		if(r<=mid) {
			return query(x*2,l,r);
		}else {
			Tree ltree,rtree;
			ltree=query(x*2,l,r);
			rtree=query(x*2+1,l,r);
			return mergeTr(ltree,rtree);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	buildTree(1,1,N);
	for(int i=1;i<=N;++i) {
		ll a;
		cin>>a;
		change(1,i,a);	// 懒得建树
	}
	for(int i=1;i<=M;++i) {
		ll op;
		cin>>op;
		if(op==1) {
			ll a,b;
			cin>>a>>b;
			if(a>b) swap(a,b);
			cout<<query(1,a,b).ans<<'\n';
		}else {
			int pos;ll s;
			cin>>pos>>s;
			change(1,pos,s);
		}
	}
	return 0;
}
/*
AC https://www.luogu.com.cn/record/199579498
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

来学习一下ST表（sparse table 稀疏表）

算了，我发现树状数组也不是不行，哈哈，我还是用我熟悉的树状数组

https://www.cnblogs.com/qdscwyy/p/9759220.html

我们来解释一些代码吧

1
2
3
4
// 1个大区间想要遍历下面的小区间需要这么写
for(int i=1;i<low;i<<=1){
	trd[x]=max(trd[x-i],trd[x]);
}

为什么需要这么写？

8→二进制100→维护区间8−lowbit(8)～88\xrightarrow{二进制}100\xrightarrow{维护区间}8-lowbit(8)～8

lowbit(8)=23=2二进制中第一个1在第几位lowbit(8)=2^3=2^{二进制中第一个1在第几位}

AC代码

AC

https://www.luogu.com.cn/record/199551454

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e4)+10;

ll N,T,H[MAXN],trx[MAXN],trd[MAXN];
inline ll lowbit(ll x){
	return x&(-x);
}
inline void updx(ll x,ll k){	// 更新小数数组
	// 将x位置替换为k
	while (x<=N) {
		trx[x]=k;
		ll low=lowbit(x);
		// 1个大区间想要遍历下面的小区间需要这么写
		for(int i=1;i<low;i<<=1){
			trx[x]=min(trx[x-i],trx[x]);
		}
		x+=lowbit(x);
	}
}
inline void updd(ll x,ll k){	// 更新大数数组
	// 将x位置替换为k
	while (x<=N) {
		trd[x]=k;
		ll low=lowbit(x);
		// 1个大区间想要遍历下面的小区间需要这么写
		for(int i=1;i<low;i<<=1){
			trd[x]=max(trd[x-i],trd[x]);
		}
		x+=lowbit(x);
	}
}
inline ll queryx(ll a,ll b){
	ll res=1e18;
	while (b>=a) {
		res=min(H[b],res);
		b-=1;
		for(;b-lowbit(b)>=a;b-=lowbit(b)){
			res=min(trx[b],res);
		}
	}
	return res;
}
inline ll queryd(ll a,ll b){
	ll res=0;
	while (b>=a) {
		res=max(H[b],res);
		b-=1;
		for(;b-lowbit(b)>=a;b-=lowbit(b)){
			res=max(trd[b],res);
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	FOR(i, 1, N){
		cin>>H[i];
	}
	memset(trx, 0x3f, sizeof(trx));
	FOR(i, 1, N){
		updd(i, H[i]);
		updx(i, H[i]);
	}
	while (T--) {
		ll l,r;
		cin>>l>>r;
		cout<<queryd(l, r)-queryx(l, r)<<'\n';
	}
	return 0;
}
/*
6 3
1
7
3
4
2
5
1 5
4 6
2 2
AC https://www.luogu.com.cn/record/199551454
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

树状数组+二分

你可以理解为用树状数组的区间加减加速模拟法（模拟法最大的瓶颈不就是区间加减吗？）

image

然后分数是只增不减的，初始分数比别人低，经过N次比赛后也不会比别人高

所以我们就能够用二分法找到区间的L，和R

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
inline ll findl(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r>>1;
		if(search(mid)>=x){
			r=mid;	// 太大了，小一点
		}else{
			l=mid+1;
		}
	}
	return l;
}
inline ll findr(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(search(mid)<=x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return l;
}

AC代码

AC

https://atcoder.jp/contests/abc389/submissions/61877078

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
	

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,MAXrange=7e5+10;

ll N,Q;
vector<pll> lr(MAXN);
ll tr[MAXrange];
inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x,ll l, ll r){
	while (l<=MAXrange) {
		tr[l]+=x;
		l+=lowbit(l);
	}
	r+=1;
	while(r<=MAXrange){
		tr[r]-=x;
		r+=lowbit(r);
	}
}
inline ll search(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline ll findl(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r>>1;
		if(search(mid)>=x){
			r=mid;	// 太大了，小一点
		}else{
			l=mid+1;
		}
	}
	return l;
}
inline ll findr(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(search(mid)<=x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return l;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>lr[i].first>>lr[i].second;
	}
	// 	初始化dp
	FOR(i, 1, MAXrange){
		// 在i～i区间上区间加i（实际上就是我懒得建树）
		add(i, i, i);
	}
	FOR(i, 1, N){
		ll l=findl(lr[i].first);
		ll r=findr(lr[i].second);
		// 如果找到的r端点的值（现在的分数）连左端点都不满足，说明查找失败
		if(search(r)<lr[i].first){
			continue;
		//  如果找到的l端点的值（现在的分数）连右端点都不满足，也说明查找失败
		}else if(search(l)>lr[i].second){
			continue;
		}
		add(1,l,r);
	}
	cin>>Q;
	FOR(_, 1, Q){
		ll x;
		cin>>x;
		cout<<search(x)<<'\n';
	}
	return 0;
}
// AC https://atcoder.jp/contests/abc389/submissions/61877078

心路历程（WA，TLE，MLE……）

提交了好多次RE，发现可能是C++23不支持宏定义了

Posted on Edited on

思路讲解

AC代码

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
#include <iostream>
using namespace std;

int parent[100002];
int order[100002];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n + 1; i++) {
        parent[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        order[i] = 0;
    }
    int current_order = 1;
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            int x = find(l);
            while (x <= r) {
                if (order[x] == 0) {
                    order[x] = current_order;
                    current_order++;
                    parent[x] = x + 1;
                }
                x = find(x);
            }
        } else if (op == 2) {
            int x;
            cin >> x;
            cout << order[x] << endl;
        }
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

Ans(需要最大化)=k1+k2+⋯+knAns(需要最大化)=k_1+k_2+\cdots+k_n

k12∗p1+k22∗p2+⋯+kn2∗pn≤Mk_1^2*p_1+k_2^2*p_2+\cdots+k_n^2*p_n\leq M

购买第 i 种产品的第 j 个花费是

(j2−(j−1)2)∗pi→化简（2j−1）∗pi(j^2-(j-1)^2)*p_i\xrightarrow{化简}（2j-1）*p_i

那不难发现，我们有一个贪心策略，就是优先买便宜的东西，再买贵的东西。

当然，直接这样搞的话，肯定TLE，我们需要找一个价格阈值x，小于x的东西我们买，大于x的东西我们就不买了，最后看总花费是否 ≤ M

https://www.luogu.com.cn/article/imo508fb 然后你会发现WA了两个点，

hack数据：

1
2
3
4
5
6
7
2 25
1 1

应该输出：
7
错误输出：
6

同样起始价格为1，有时要买3个，有时要买4个，那怎么解决？

加了下面的小根堆就万无一失了，因为我们将刚刚超过价格阈值的全部记录下来，再跑一遍看看有没有遗失的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
ll cost=0;
for(int i=1;i<=N;++i){
	ll j=(l/P[i]+1)/2;
	cost+=j*j*P[i];
	pq.push((2*(j+1)-1)*P[i]);
}
while (!pq.empty()) {
	if(cost+pq.top()>M){
		break;
	}else{
		ans+=1;
		cost+=pq.top();
		pq.pop();
	}
}
cout<<ans<<'\n';

AC代码

AC https://atcoder.jp/contests/abc389/submissions/61888808

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef unsigned long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;

ll N,M,P[MAXN],ans;
// 小根堆
priority_queue<ll , vector<ll>, greater<ll>> pq;

inline bool check(ll x){
	ll cost=0,res=0;
	for(int i=1;i<=N;++i){
		ll j=(x/P[i]+1)/2;
		if(j==0)	// 防除零
			continue;
		// 防溢出
		if(j*P[i] > (M-cost)/j){
			return false;
		}
		cost+=j*j*P[i];
		res+=j;
		if(cost>M){
			return false;
		}
	}
	ans=max(ans,res);
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;++i){
		cin>>P[i];
	}
	sort(&P[1],&P[N+1]);
	ll l=0,r=M;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
	ll cost=0;
	for(int i=1;i<=N;++i){
		ll j=(l/P[i]+1)/2;
		cost+=j*j*P[i];
		pq.push((2*(j+1)-1)*P[i]);
	}
	while (!pq.empty()) {
		if(cost+pq.top()>M){
			break;
		}else{
			ans+=1;
			cost+=pq.top();
			pq.pop();
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
2 25
1 1
AC https://atcoder.jp/contests/abc389/submissions/61888808
*/

心路历程（WA，TLE，MLE……）