Znzryb's Blog
0%

Posted on Edited on

思路讲解

https://ac.nowcoder.com/discuss/1452662

主要就是他的思路，赛时实际上就AC了，只不过赛后数据加强了，前面AI乱写的过不去了。

这个思路就是贪心，先把最小的吃掉，再吃次小的，再吃次次小的。。。。以此类推

AC代码

AC

https://ac.nowcoder.com/acm/contest/95323/M

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
#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>(1e5)+10,maxval=static_cast<ll>(1e18)+3;
ll N,T,A[MAXN];
multiset<ll> st;
vector<pll> Apos;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll maxA=0,minA=maxval;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		st.insert(A[i]);
		Apos.push_back({A[i],i});
	}
	sort(Apos.begin(),Apos.end());
	st.insert(*st.begin()*2);
	st.erase(st.begin());
	ll ans=*st.rbegin()-*st.begin();
	ll l=Apos[0].second,r=Apos[0].second;
	for(int i=1;i<N;++i) {
		ll pos=Apos[i].second,key=Apos[i].first;
		if(l<=pos && pos<=r) continue;
		if(pos<l) {
			ll l1=pos;
			for(int j=l1;j<l;++j) {
				auto it=st.lower_bound(A[j]);
				st.insert(*it*2);
				st.erase(it);
			}
			l=l1;
		}else {
			ll r1=pos;
			for(int j=r+1;j<=r1;++j) {
				auto it=st.lower_bound(A[j]);
				st.insert(*it*2);
				st.erase(it);
			}
			r=r1;
		}
		ans=min(ans,*st.rbegin()-*st.begin());
	}
	cout<<ans<<endl;
	return 0;
}
/*
5
9 3 5 3 9

*/

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

Posted on Edited on

思路讲解

参考题解：

https://ac.nowcoder.com/discuss/1452661

https://ac.nowcoder.com/discuss/1452662（这个题解好）

中位数定理，其实类似于树的重心（以该点为根，最大子树最小），都是不能牺牲大我

只有一个点左边也有n个点，右边也有n个点，到达该点距离之和最短

其实数轴就是一种特殊的树嘛～～

AC代码

AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74961575

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
#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>(1e5)+10;
ll N,T,A[MAXN];
void solve() {
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    sort(&A[1],&A[N+1]);
    // 中位数定理
    ll mid1,mid2;
    if(N%4==0) mid1=A[N/4]+A[N/4+1]>>1,mid2=A[3*N/4]+A[3*N/4+1]>>1;
    else mid1=A[N/4+1],mid2=A[3*N/4+1];	// 是不是严格在中间是不重要的
    if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }
    ll dis=0;
    for(int i=1;i<=N;++i) {
        if(i<=N/2) {
            dis+=abs(A[i]-mid1);
        }else {
            dis+=abs(A[i]-mid2);
        }
    }
    cout<<dis<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
3
4
1 1 3 1
4
6 6 6 6
6
1 1 4 4 1 4

*/

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

前面一直有点问题，结果是因为这个特判mid1-=1和mid2+=1都要算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }

Posted on Edited on

思路讲解

FHQ-Treap

https://www.luogu.com.cn/article/vj041eul

AC代码

AC

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

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
129
130
131
132
133
134
135
136
#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>(4e6) + 10;
ll N, M, idx, root, last, ans;
mt19937 rng(time(0));
//                          值         随机值
ll son[MAXN][2], size[MAXN], key[MAXN], rad[MAXN];
inline void resize(ll k) { size[k] = size[son[k][0]] + size[son[k][1]] + 1; }
// split函数返回的是分裂出来的左子树和右子树的编号
//          根与按值分裂的值
pll split(ll u, ll k) {
    // 这里按值分裂,分裂为左子树<k，右子树>=k;
    if (!u)
        return {0, 0}; // 递归终止条件
    if (key[u] < k) {
        // 继续分裂右子树（左子树全部<k，也都符合条件）
        pll t = split(son[u][1], k);
        son[u][1] = t.first;
        resize(u); // 重新计算树大小
        // 进入到了这个节点，就是来找左子树中有没有>=k的值的
        return {u, t.second};
    } else {
        // 继续分裂左子树（右子树全部>=k，都符合条件）
        pll t = split(son[u][0], k);
        son[u][0] = t.second;
        resize(u);
        // 进入到了这个节点，就是来找右子树中有没有<k的值的，右子树中<k的值的就是在左子树
        return {t.first, u};
    }
}
// merge函数接受两个参数，为两棵树的根；返回合并后的根。
ll merge(ll u, ll v) {
    if (!u | !v)
        return u + v; // 如果任何一棵树为空，返回另一棵树
    if (rad[u] < rad[v]) {
        // 小根堆，我们让随机值小的u当根，merge左子树
        son[u][1] = merge(son[u][1], v);
        resize(u);
        return u;
    } else {
        // u值比较大，当v的右边
        son[v][0] = merge(u, son[v][0]);
        resize(v);
        return v;
    }
}
inline void insert(ll k) {
    key[++idx] = k;
    rad[idx] = rng();
    size[idx] = 1;
    pll t = split(root, k);
    root = merge(merge(t.first, idx), t.second);
}
inline void eraser(ll k) {
    pll x = split(root, k);
    // x.second 是所有>=k的，所以y就分成了=k的和>k的
    pll y = split(x.second, k + 1);
    // 把=k的根节点吃掉了
    y.first = merge(son[y.first][0], son[y.first][1]);
    // 依次合并起来，更新根
    root = merge(x.first, merge(y.first, y.second));
}
// 查询k的排名
inline ll find1(ll k) {
    pll t = split(root, k);
    ll rank = size[t.first] + 1;
    root = merge(t.first, t.second);
    return rank;
}
// 根据排名找数
inline ll find2(ll rank) {
    ll pos = root;
    while (pos) {
        if (rank == size[son[pos][0]] + 1)
            return key[pos];
        else if (size[son[pos][0]] + 1 > rank)
            pos = son[pos][0];
        else
            rank -= size[son[pos][0]] + 1, pos = son[pos][1];
    }
    return 0;
}
// 查询前驱
inline ll lst(ll k) { return find2(find1(k) - 1); }
// 直接find1(k+1)，查询的值+1，避免了值相同的问题
inline ll nxt(ll k) { return find2(find1(k + 1)); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        insert(a);
    }
    // cout<<"debug "<<0<<" :\n";
    // cout<<root<<'\n';
    // for(int j=1;j<=N;++j) {
    //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
 // }
 for(int i=1;i<=M;i++){
  ll o,x;
  cin>>o>>x;
  // x^=last;
  if(o==1) insert(x^last);
  if(o==2) eraser(x^last);
  if(o==3) { last=find1(x^last); ans^=last; }
  if(o==4) { last=find2(x^last); ans^=last; }
  if(o==5) { last=lst(x^last); ans^=last; }
  if(o==6) { last=nxt(x^last); ans^=last; }
  // cout<<"debug "<<i<<" :\n";
  // for(int j=1;j<=N;++j) {
  //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
  // }
 }
 cout<<ans<<endl;
 return 0;
}
/*
AC https://www.luogu.com.cn/record/200519720
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4

*/

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

各种奇怪的地方吧，导致WA了。

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……）