• 格式
1
2
// 题目来源 ， 什么算法 
// 提交代码

2023-11-27

异或树

cf CF1658D2 388535 (Hard Version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
int T,l,r,a[N],cnt,trie[N][30],b[N];
void insert(int sum){
	int now=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp])trie[now][tmp]=++cnt;
		now=trie[now][tmp];
	}
}
int Max(int sum){
	int now=0,res=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp^1])now=trie[now][tmp];
		else now=trie[now][tmp^1],res+=(1<<i);
	}
	return res;
}
int Min(int sum){
	int now=0,res=0;
	for(int i=17;i>=0;i--){
		bool tmp=(1<<i)&sum;
		if(!trie[now][tmp])now=trie[now][tmp^1],res+=(1<<i);
		else now=trie[now][tmp];
	}
	return res;
}

floyd

预赛

1
2
3
4
5
6
7
for(int k = 1; k <= n; ++k){
    for(int i = 1; i <= n; ++i)){
        for(int j = 1; j <= n; ++j){
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
        }
    }
}

拓扑排序

cf Codeforces Round 897 (Div. 2) A - F - 知乎 (zhihu.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto dfs = [&](auto &&dfs, int u, int from) -> void {
    v[u] = true;
    ins[u] = true;
    for(auto [j, id] : g[u]){
        if (id == from) continue;
        if (!v[j]) dfs(dfs, j, id);
        else if (ins[j]){
            int t = j;
            cycle.clear();
            cycle.push_back(j);
            while(1){
                t = a[t];
                if (t == j) break;
                cycle.push_back(t);
            }
        }
    }
    ins[u] = false;
};

2023-11-28

拓扑排序

CF CF1593E Gardener and Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void toposort() {
    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 1) {
            q.push(i);
            rnk[i] = 1;
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];

            if(--deg[v] == 1) {
                rnk[v] = rnk[u] + 1;
                q.push(v);
            }
        }
    }
}

分治

leetcode 932. 漂亮数组 - 力扣（LeetCode）

奇数 + 偶数 等于 奇数

题目的原理， 可以进行映射处理， 所有，对于每一层

image-20231128102547476

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
class Solution {
public:
    unordered_map<int,vector<int> > mp;
    vector<int> beautifulArray(int N) {
        return f(N);
    }
    vector<int> f(int N) {
        vector<int> ans(N, 0);
        int t = 0;
        if (mp.find(N) != mp.end()) {
            return mp[N];
        }
        if (N != 1) {
            for (auto x : f((N+1)/2)){
                ans[t++]= 2 * x - 1;
            } 
            for (auto x : f(N/2)){
                ans[t++] =  2 * x;
            }
        }else {
            ans[0] = 1;
        }
        mp[N] = ans;
        return ans;
    }
};

构造题

CF Problem - 1582D - Codeforces

构造题目， 需要大胆猜测， 这里说全部加起来为0， 这有点难想， 但是转换更小的情况取思考） 我们设 b i + 1 = ai， bi = ai + 1， 这样子就会好像很多了

2023-11-29

数据结构 ， 规律

CF CF1899F Alex’s whims - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

a[i] = i + 1这种处理数据结构的方式， 可以解决那种 一个点， 后面的所有点， 移动到另外一个点的后面, 而且需要记录节点编号

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')y=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x*y;

}
const int N=5e2+7;
ll T,n,q,u[N],ut,v[N],vt;
void moveu(ll y){
	ll U,V1,V2;
	U=u[ut-y+1];
	V1=u[ut-y];
	V2=v[vt];
	printf("%lld %lld %lld\n",U,V1,V2);
	for(int i=ut-y+1;i<=ut;i++)
		v[++vt]=u[i];
	ut-=y; 
}
void movev(ll y){
	ll U,V1,V2;
	U=v[vt-y+1];
	V1=v[vt-y];
	V2=u[ut];
	printf("%lld %lld %lld\n",U,V1,V2);
	for(int i=vt-y+1;i<=vt;i++)
		u[++ut]=v[i];
	vt-=y;
}
int main(){
	T=read();
	u[1]=v[1]=2;
	while(T--){
		n=read();q=read();
		for(int i=1;i<n;i++)
			printf("%d %d\n",i,i+1);
		ut=n-1;
		for(int i=2;i<=ut;i++)
			u[i]=i+1;
		vt=1;
		while(q--){
			ll x=read();
			if(x==vt||x==ut)printf("-1 -1 -1\n");
			else{
				if(x>ut) movev(x-ut);
				else moveu(ut-x);
			}
		}
	}
	return 0;
}

2023-11-30

逆序对

CF Codeforces Global Round 16 - 知乎 (zhihu.com)

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
#include <bits/stdc++.h>
 
int t, n, m;
std::vector<std::pair<int, int>> a;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        a.resize(n*m);
        for (int i = 0; i < n * m; ++i) scanf("%d", &a[i].first), a[i].second = i;
        std::sort(a.begin(), a.end());
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) a[i*m+j].second *= -1;
            std::sort(a.begin()+i*m, a.begin()+(i+1)*m);
            for (int j = 0; j < m; ++j) {
                for (int k = 0; k < j; ++k)
                    if (a[i*m+k].second > a[i*m+j].second) ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

回文串

CF CF1555D Say No to Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • 一开始就可以取考虑 循环 串的方向，

    然后我们发现一个字符串如果不按照 abc 的全排列构成的循环串 就不可能实现回文

    所以考虑把当i个字符串变成abc 全排列的一种，需要消耗多少费用， 然后来解决这个问题。（别再当蠢猪了）

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
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 2e5 + 10;

int n,m;
int sum[7][N];
string s;

void work(char x , char y , char z , int t)
{
    for(int i = 0; i < n; i++)
    {
        sum[t][i + 1] += sum[t][i];
        if(i % 3 == 0 && s[i] != x) sum[t][i + 1]++;
        if(i % 3 == 1 && s[i] != y) sum[t][i + 1]++;
        if(i % 3 == 2 && s[i] != z) sum[t][i + 1]++;
    }
}

int main()
{
  //  freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&m);
    cin >> s;

    work('a' , 'b' , 'c' , 1);
    work('b' , 'a' , 'c' , 2);
    work('c' , 'a' , 'b' , 3);
    work('c' , 'b' , 'a' , 4);
    work('a' , 'c' , 'b' , 5);
    work('b' , 'c' , 'a' , 6);

    for(int i = 1; i <= m; i++)
    {
        int l , r; scanf("%d%d",&l,&r);
        int ans = 1e9 + 10;
        for(int j = 1; j <= 6; j++)
            ans = min(ans , sum[j][r] - sum[j][l - 1]);
        printf("%d\n",ans);
    }
}

数学

CF CF1542C Strange Function - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

如果一个数， 可以被 1， 2， 3， 4， 5 ， 6 除， 那么这个数最小是多少， 1 * 2 * 3 * 4 * 5 * 6， 然后一个这个单位增加的数， 依旧满足这个特征， 那么我们就可以计算出来， 一个数x里面有多少个 可以 被 1 ~ 6 相除的个数

image-20231130190804898

2023-12-1

构造题， 字符串

CF Erase and Extend (Hard Version) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

直接从长度为 0 开始往后构造数组就好了

1
2
3
4
5
6
7
8
9
10
11
12
int main() {
    n = read(); K = read();
    cin >> s;
    int p = 1, i = 0, n = s.length();
    for (; i < n; ++ i) {
        if (s[i] > s[i % p]) break;
        if (s[i] < s[i % p]) p = i + 1;
    }
    for (i = 0; i < K; ++ i) putchar(s[i % p]);
    puts("");
    return 0;
}

数学

CF CF1603B Moderate Modular Mode - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

image-20231201233232623

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main(){
	int T; cin>>T;
	while(T--){
		int x,y; cin>>x>>y;
		if(x>y) cout<<x+y<<endl;
		else if(x==y) cout<<x<<endl;
		else cout<<y-(y%x)/2<<endl;
	}return 0;
}

2023-12-3

思维题

leetcode 100153. 需要添加的硬币的最小数量 - 力扣（LeetCode）

  • 一开始想成了背包问题，实际上不是， 考虑一个情况， 如果 你能凑出前m个元素， 当前元素是x，
    • 如果x 《= m， 那么 【1， m + x】，你都可以凑出来
    • 否则， 我们在添加一个m， 尽可能扩大元素， 使得后面的x 《= m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        Arrays.sort(coins);
        int addedCoins = 0;
        int value = 1;
        int m = coins.length;
        int index = 0;
        while (value <= target) {
            if (index < m && coins[index] <= value) {
                value += coins[index];
                index++;
            } else {
                addedCoins++;
                value *= 2;
            }
        }
        return addedCoins;
    }
}

滑动窗口 模拟题

leetcode 100145. 统计完全子字符串 - 力扣（LeetCode）

  • 这道题目， 一开始就往 哈希的方向去想， 但是这是错误， 因为 当前cur 可能可以与多种情况进行匹配（分类思考能力不行），
  • 实际上这题就是枚举 不同字符的个数， 这个时候窗口的长度就已经固定住了， 那么就直接最基础的滑动窗口就可以过掉了
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
class Solution {
    int f(string s, int k) {
        int res = 0;
        for (int m = 1; m <= 26 && k * m <= s.length(); m++) {
            int cnt[26]{};
            auto check = [&]() {
                for (int i = 0; i < 26; i++) {
                    if (cnt[i] && cnt[i] != k) {
                        return;
                    }
                }
                res++;
            };
            for (int right = 0; right < s.length(); right++) {
                cnt[s[right] - 'a']++;
                int left = right + 1 - k * m;
                if (left >= 0) {
                    check();
                    cnt[s[left] - 'a']--;
                }
            }
        }
        return res;
    }

public:
    int countCompleteSubstrings(string word, int k) {
        int n = word.length();
        int ans = 0;
        for (int i = 0; i < n;) {
            int st = i;
            for (i++; i < n && abs(int(word[i]) - int(word[i - 1])) <= 2; i++);
            ans += f(word.substr(st, i - st), k);
        }
        return ans;
    }
};

数学

leetcode 100146. 统计感冒序列的数目 - 力扣（LeetCode）

  • 没时间看了
  • 就是第一种是 序列之间各个元素之间的插入顺序（然后这个时候插入的元素还没有指定是序列中的哪一个元素），然后第二部在对同一个序列之内进行方案计算
1
2
3
4
5
6
fac[0]=1;
for(int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%p;
ifac[n]=qpow(fac[n],p-2);
for(int j=n-1;j>=0;j--)
    ifac[j]=ifac[j+1]*(j+1)%p;

2023-12-4

数学题

CF Problem - D - Codeforces

考虑下面几个等式

我们就可以推出结论， 然后二分判断 即可

0fc3725a6c1fc6ee2458cc4a295add1

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
map<pair<int,int>,vector<int> >V;
inline bool Ask(re int x,re int y,re int l,re int r){
	pair<int,int>tmp=make_pair(x,y);
	int o=lower_bound(V[tmp].begin(),V[tmp].end(),l)-V[tmp].begin();
	if(o>=V[tmp].size())return 0;
	return V[tmp][o]<=r;
}
int main(){
	n=read(),m=read();
	scanf("%s",s+1);
	for(re int i=1;i<=n;++i){
		X[i]=X[i-1],Y[i]=Y[i-1];
		if(s[i]=='R')++X[i];
		else if(s[i]=='L')--X[i];
		else if(s[i]=='U')++Y[i];
		else --Y[i];
	}
	for(re int i=0;i<=n;++i)V[make_pair(X[i],Y[i])].push_back(i);
	while(m--){
		re int x=read(),y=read(),l=read(),r=read();
		if(Ask(x,y,0,l-1))puts("YES");
		else if(Ask(x,y,r,n))puts("YES");
		else if(Ask(X[l-1]*2+(X[r]-X[l-1])-x,Y[l-1]*2+(Y[r]-Y[l-1])-y,l,r))puts("YES");
		else puts("NO");
	}
	
}

模拟题

CF Standings - Codeforces Round 910 (Div. 2) - Codeforces

题目思路不难想， 但是代码有点难写， 就在结尾设置可以绕圈的地方就好了

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
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    if (k < n - 1 + m - 1) {
        cout << "NO\n";
        return;
    }
    if (k % 2 != (n + m) % 2) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    for (int t = 0; t < n; ++t) {
        for (int i = 0; i < m - 1; ++i) {
            if (i % 2 == 0) {
                cout << "R ";
            } else {
                cout << "B ";
            }
        }
        cout << "\n";
    }
    char ch = (m % 2 == 0 ? 'B' : 'R');
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i % 2 == 1 && j == m - 1) {
                char c = 'B' + 'R' - ch;
                cout << c << " ";
            } else {
                cout << ch << " ";
            }
        }
        cout << "\n";
    }
}

2023-12-5

二分

CF Problem - D - Codeforces

  • 想到了二分，但是不知道怎么写check函数， 实际上，就是把他能走到的边界算出来就好了

模拟题

CF Problem - F - Codeforces

  • 知道怎么做，但是就是打不出来代码， 实际上观察可以发现， 满足添加的模型一定满足 (a[i] <= (a[(i + 1) %n])) <= 1或者 (a[i] >= (a[(i + 1) %n])) <= 1
  • 然后就好搞了

思维题

CF Problem - E - Codeforces

  • 实际上这题 你可以这么想如果我想要进位， 那么就得dig就是当前位加上10， 那么对于下一位因为进位了， 所以我可以少要1， 但是你的dig 还是多出来了 9个， 我们不可能从前面省下来

2023-12-6

线段树

CF Ones and Twos - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) A - E - 知乎 (zhihu.com)

image-20231207133657587

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
137
138
139
140
141
142
143
144
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
#include<array>
using namespace std;
using LL = long long;
const int INF = 1e9;
struct Info {
    array<int, 2> mx = {0, -INF}, ls = {0, -INF}, rs = {0, -INF};
    int sum = 0;
};

Info operator+(const Info &a, const Info &b){
    Info ret = {};
    ret.sum = a.sum + b.sum;
    for(int i = 0; i < 2; i++){
        ret.mx[i] = max(a.mx[i], b.mx[i]);
        ret.ls[i] = max(a.ls[i], a.sum + b.ls[i ^ (a.sum % 2)]);
        ret.rs[i] = max(b.rs[i], b.sum + a.rs[i ^ (b.sum % 2)]);
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            ret.mx[i ^ j] = max(ret.mx[i ^ j], a.rs[i] + b.ls[j]);
        }
    }
    return ret;
}

template<class Info>
struct SegmentTree{
    int n;
    vector<Info> info;

    SegmentTree() {}

    SegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    SegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v){
        modify(1, 1, n, p, v);
    }

    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }

    Info query(int l, int r){
        return query(1, 1, n, l, r);
    }
};

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const Info init1 = {{0, 1}, {0, 1}, {0, 1}, 1};
    const Info init2 = {{2, -INF}, {2, -INF}, {2, -INF}, 2};

    int T;
    cin >> T;
    while(T--){
        int n, q;
        cin >> n >> q;
        vector<int> a(n + 1);
        vector<Info> init(n);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            init[i - 1] = (a[i] == 1 ? init1 : init2);
        }
        SegmentTree<Info> seg(init);
        while(q--){
            int op;
            cin >> op;
            if (op == 1){
                int s;
                cin >> s;
                auto ans = seg.query(1, n);
                if (ans.mx[s % 2] >= s){
                    cout << "YES" << '\n';
                }
                else{
                    cout << "NO" << '\n';
                }
            }
            else{
                int x, v;
                cin >> x >> v;
                seg.modify(x, v == 1 ? init1 : init2);
            }
        }
    }

}

2023-12-7

线段树 思维

CF CF1884C Medium Design - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

反正就是线段树各种骚操作就完了

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
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int lsh[MAXN<<1],chafen[MAXN<<1],a[MAXN<<1],n,m,b[MAXN<<1];
struct line{
	int l,r;
	bool operator<(const line x)const{
		return r>x.r;
	}
}li[MAXN];
priority_queue<line>q;
struct linetree{
	int l,r,minv,lazy;
}lt[MAXN<<3];
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x;
}
void buildtree(int id,int l,int r){
	if(l==r){
		lt[id].l=lt[id].r=l;
		lt[id].lazy=lt[id].minv=0;
		return;
	}
	int lid=id<<1,rid=lid+1,mid=(l+r)>>1;
	buildtree(lid,l,mid);buildtree(rid,mid+1,r);
	lt[id].l=l;lt[id].r=r;
	lt[id].lazy=lt[id].minv=0;
}
void pushdown(int id){
	if(lt[id].lazy){
		int lid=id<<1,rid=lid+1;
		lt[lid].lazy+=lt[id].lazy;
		lt[rid].lazy+=lt[id].lazy;
		lt[id].lazy=0;
		lt[id].minv=min(lt[lid].minv+lt[lid].lazy,lt[rid].minv+lt[rid].lazy);
	}
}
void pushup(int id){
	int lid=id<<1,rid=lid+1;
	lt[id].minv=min(lt[lid].minv+lt[lid].lazy,lt[rid].minv+lt[rid].lazy);
}
void linetree_add(int id,int l,int r,int k){
	if(lt[id].l==l&&lt[id].r==r){
		lt[id].lazy+=k;
		return;
	}
	pushdown(id);
	int lid=id<<1,rid=lid+1;
	if(r<=lt[lid].r){
		linetree_add(lid,l,r,k);
	}
	else if(l>=lt[rid].l){
		linetree_add(rid,l,r,k);
	}
	else{
		linetree_add(lid,l,lt[lid].r,k);
		linetree_add(rid,lt[rid].l,r,k);
	}
	pushup(id);
}
int linetree_query(int id,int l,int r){
	if(lt[id].l==l&&lt[id].r==r){
		return lt[id].minv+lt[id].lazy;
	}
	pushdown(id);
	int lid=id<<1,rid=lid+1;
	if(r<=lt[lid].r)return linetree_query(lid,l,r);
	else if(l>=lt[rid].l)return linetree_query(rid,l,r);
	else return min(linetree_query(lid,l,lt[lid].r),linetree_query(rid,lt[rid].l,r));
}
bool cmp(line x,line y){
	return x.l<y.l;
}
int main(){
	int t=read();
	while(t){
		--t;
		while(!q.empty())q.pop();
		memset(chafen,0,sizeof(chafen));
		n=read();m=read();
		int lshcnt=0;
		for(int i=1;i<=n;++i){
			lsh[++lshcnt]=li[i].l=read();
			lsh[++lshcnt]=li[i].r=read();
		}
		lsh[++lshcnt]=1;lsh[++lshcnt]=m;
		sort(lsh+1,lsh+lshcnt+1);
		int lshn=unique(lsh+1,lsh+lshcnt+1)-(lsh+1);
		for(int i=1;i<=n;++i){
			li[i].l=lower_bound(lsh+1,lsh+lshn+1,li[i].l)-lsh;
			li[i].r=lower_bound(lsh+1,lsh+lshn+1,li[i].r)-lsh;
			chafen[li[i].l]+=1;chafen[li[i].r+1]-=1;
		}
		for(int i=1;i<=lshn;++i){
			a[i]=a[i-1]+chafen[i];
		}
		buildtree(1,1,lshn);
		sort(li+1,li+1+n,cmp);
		int ans=0,p=1;
		for(int i=1;i<=lshn;++i){
			while(p<=n&&li[p].l<=i){
				linetree_add(1,li[p].l,li[p].r,1);
				q.push(li[p]);
				++p;
			}
			while(!q.empty()&&q.top().r<i){
				linetree_add(1,q.top().l,q.top().r,-1);
				q.pop();
			}
			ans=max(ans,a[i]-linetree_query(1,1,lshn));
		}
		printf("%d\n",ans);
	}
	return 0;
}

2023-12-8

数学题

CF CF1889B Doremy’s Connecting Plan - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

只能说太强了， 根本想不出这个解法

image-20231209114600767