2021GDCPC题解(12/12)

2021GDCPC题解(12/12)

这场感觉挺无聊的，都是典题，而且很多题怪怪的

A. An Easy Problem

思路：经典k路归并排序，对于任意一个i属于 [ 1 , n ] [1, n] [1,n], 若固定i，则j从 [ m , 1 ] [m, 1] [m,1]是单调递减的，所以我们可以事先将所有i属于 [ 1 , n ] [1, n] [1,n]， j = m j = m j=m的 k k k路起点丢进堆中, 每次弹出最大值，同时更新对应路的指针即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    priority_queue<pair<ll, int>> q;
    for (int i = 1; i <= n; ++i) {
        q.emplace(i * m, m);
    }
    ll ans = 0;
    for (int i = 1; i <= k; ++i) {
        auto [x, y] = q.top();
        q.pop();
        ans = x;
        q.emplace(x / y  * (y - 1), y - 1);
    }
    cout << ans;
    return 0;
}

B. Byfibonacci

思路：其实就是个物品质量为 f i b fib fib数的01背包，斐波那契前缀和有个经典结论， ∑ i = 1 n f i b ( i ) = f i b ( n + 2 ) − 1 \sum\limits_{i = 1} ^ {n} fib(i) = fib(n + 2) -1 i=1∑n​fib(i)=fib(n+2)−1, 故 s u m ( i ) < 3 f i b ( i ) sum(i) < 3fib(i) sum(i)<3fib(i)，所以可以 以 2 ∑ i = 1 n f i b ( i ) , ∑ f i b ( i ) < 1 e 7 以2\sum\limits_{i = 1} ^ {n} fib(i), \sum fib(i) < 1e7 以2i=1∑n​fib(i),∑fib(i)<1e7的情况通过此题。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
const int maxn = 1e7 + 5;
const int M = 1e7;
const int mod = 998244353;
int dp[maxn], f[maxn];

void read(int&x) {
    char c = getchar();
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
}

int main() {
    int T;
    f[1] = 1;
    for (int i = 2; i <= 36; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }
    dp[0] = dp[1] = 1;
    // int cnt = 0;
    for (int i = 2; i <= 36; ++i) {
        for (int j = min(3 * f[i], M); j >= f[i]; --j) {
            dp[j] = (dp[j] + (ll)f[i] * dp[j - f[i]]) % mod;
            // cnt++;
        }
    }
    // cout << cnt;
    read(T);
    for (int i = 1; i <= T; ++i) {
        int n;
        read(n);
        cout << dp[n] << "\n";
    }
    return 0;
}

C. Conspicuousness

思路： s a m sam sam板子题，在建 s a m sam sam的时候记录串的出现次数，按 p a r e n t s parents parents树上的拓扑序更新再做后缀和即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
const int maxn = 6e5 + 5;
struct SAM {
    int len[maxn], link[maxn], ch[maxn][26], last, tot, sz[maxn];
    int tax[maxn], rk[maxn];
    ll sum[maxn];
    SAM() {
        tot = last = 1;
    }
    void extend(int c) {
        int cur = ++tot, p = last; last = cur;
        sz[cur] = 1;
        len[cur] = len[p] + 1;
        for (; p && !ch[p][c]; p = link[p]) {
            ch[p][c] = cur;
        }
        if (!p)
            link[cur] = 1;
        else {
            int q = ch[p][c];
            if (len[p] + 1 == len[q])
                link[cur] = q;
            else {
                int clone = ++tot;
                memcpy(ch[clone], ch[q], sizeof(ch[q]));
                len[clone] = len[p] + 1;
                link[clone] = link[q];
                link[q] = link[cur] = clone;
                for (; p && ch[p][c] == q; p = link[p]) 
                    ch[p][c] = clone;
            }
        }
    }
    void solve(int x) {
        for (int i = 1; i <= tot; ++i) 
            tax[len[i]]++;
        for (int i = 1; i <= x; ++i)
            tax[i] += tax[i - 1];
        for (int i = 1; i <= tot; ++i)
            rk[tax[len[i]]--] = i;
        for (int i = tot; i; --i) {
            int now = rk[i];
            sz[link[now]] += sz[now];
        }
        sz[1] = 0;
        for (int i = 1; i <= tot; ++i) {
            sum[len[i]] = max(sum[len[i]], (ll)sz[i]);
        }
        for (int i = x - 1; i >= 1; --i) {
            sum[i] = max(sum[i + 1], sum[i]);
        }
    }
} sam;

char s[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    cin >> (s + 1);
    int len = strlen(s + 1);
    for (int i = 1; i <= len; ++i) {
        sam.extend(s[i] - '1');
    }
    sam.solve(len);
    for (int i = 1; i <= q; ++i) {
        int k;
        cin >> k;
        cout << sam.sum[k] << "\n";
    }
    return 0;
}

D. Double

思路：暴力判断每个点是否能扩展为1e9即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
const int maxn = 5e5 + 5;
int n, a[maxn];

int main() {
    IOS
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        ll sum = a[i];
        int l = i - 1, r = i + 1;
        while (sum < 1e9) {
            if (l >= 1 && a[l] <= sum) {
                sum *= 2;
                l--;
            } else if(r <= n && a[r] <= sum) {
                r++;
                sum *= 2;
            } else {
                break;
            }
        }
        if ((!l && r == n + 1) || sum >= 1e9) {
            ans.emplace_back(i);
        }
    }
    cout << ans.size() << '\n';
    for (auto u : ans) {
        cout << u << " ";
    }
    return 0;
}

E. EXcellent Number

思路：显然有一个裸的数位 d p dp dp， d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当前枚举到第 i i i位，数字模 11 11 11的值位 j j j，已经匹配了 k k k位的方案数，转移的时候用 k m p kmp kmp处理出 n x t [ i ] [ j ] nxt[i][j] nxt[i][j]表示已经匹配 i i i位下一个数字加 j j j时的最长匹配长度，来优化该转移，但时间复杂度为O ( 1 e 6 ∗ 11 ∗ 1 0 2 ) (1e6 * 11 * 10 ^ 2) (1e6∗11∗102), 时间和空间均无法承受，我们考虑特判 1 0 n 10^n 10n后，对于第一维的递推都是一致的，第一维可以使用矩阵快速幂优化，具体来说就是构造一个 11 l o g k ∗ 11 l o g k 11logk * 11logk 11logk∗11logk的矩阵A,

A [ d p [ 0 ] [ 0 ] d p [ 0 ] [ 1 ] d p [ 0 ] [ 2 ] . . . . ] = [ d p [ 0 ] [ 0 ] d p [ 0 ] [ 1 ] d p [ 0 ] [ 2 ] . . . . ] A\left[\begin{matrix}dp[0][0]\\dp[0][1] \\dp[0][2]\\....\end{matrix} \right] = \left[\begin{matrix}dp[0][0]\\dp[0][1] \\dp[0][2]\\....\end{matrix} \right] A ​dp[0][0]dp[0][1]dp[0][2]....​ ​= ​dp[0][0]dp[0][1]dp[0][2]....​ ​, 我们暴力枚举第二三维以及下一个填的数字通过 n x t nxt nxt在A中构造矩阵即可，不懂的可以看代码。时间复杂度 O ( ( 11 l o g k ) 3 l o g ( n ) ) O((11logk) ^ 3 log(n)) O((11logk)3log(n)), 足以通过本题, 感觉自己真的老了，推个转移矩阵还算了半天。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;

int M;
int n, num, dig[13], fail[13], nxt[11][11];
const int maxn = 8e5 + 5;
int dp[maxn][11][7];

void ADD(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}

// int dfs(int pos, int mo, int len, bool limit) {
//     if (!pos)
//         return (!mo || len >= num);
//     if (!limit && ~dp[pos][mo][len])
//         return dp[pos][mo][len];
//     int up = 9;
//     int ans = 0;
//     for (int i = 0; i <= up; ++i) {
//         if (len < num && dig[len + 1] == i) {
//             ADD(ans, dfs(pos - 1, (mo * 10 + i) % 11, len + 1, limit && (i == up)));
//         } else if (len == num) {
//             ADD(ans, dfs(pos - 1, (mo * 10 + i) % 11, len, limit && (i == up)));
//         } else {
//             ADD(ans, dfs(pos - 1, (mo * 10 + i) % 11, nxt[len][i], limit && i == up));
//         }
//     }
//     if (!limit)
//         dp[pos][mo][len] = ans;
//     return ans;
// }
struct Mat{
	int a[120][120];
	void clear(){
        memset(a, 0, sizeof a);
    }
	void init()
	{
		memset(a, 0, sizeof a);
		for(int i = 1; i <= M; i++)
			a[i][i] = 1;
	}
};

Mat operator *(const Mat &x, const Mat &y){
	Mat res;
	res.clear();
	for(int i = 1; i <= M; i++){
		for(int j = 1; j <= M; j++){
			for(int k = 1; k <= M; k++){
				res.a[i][j] = (res.a[i][j] +  (ll)x.a[i][k] * y.a[k][j]) % mod;
			}
		}
	}
	return res;
}

Mat mypow(Mat a, int b){
	Mat ans;
	ans.init();
	while(b){
		if(b & 1)
			ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}

void KMP() {
    fail[1] = 0;
	for(int i = 2, j = 0; i <= num; ++i) {
		while(j && dig[j + 1] != dig[i])
			j = fail[j];
		if(dig[j + 1] == dig[i])
			++j;
		fail[i] = j;
	}
	for(int i = 0; i <= num; ++i){
		for(int j = 0; j <= 9; ++j){
			if(i == num)
				nxt[i][j] = num;
			else{
				int k = i;
				while(k && dig[k + 1] != j)
					k = fail[k];
				if(dig[k + 1] == j)
					++k;
				nxt[i][j] = k;
			}
		}
	}
}

void solve() {
	int k;
	cin >> n >> k;
	num = 0;
	while(k) {
		dig[++num] = k % 10;
        k /= 10; 
    }
	reverse(dig + 1, dig + num + 1);
	ll ans = 0;
	if(num <= n + 1){
		ans = 1;
		if(dig[1] != 1)
			ans = 0;
		for(int i = 2; i <= num; i++)
			if(dig[i] != 0)
                ans = 0;
	}
    KMP();
	M = (num + 1) * 11;
	Mat dp;
	dp.clear();
	for(int i = 0; i <= num; ++i)
	{
		for(int j = 0; j <= 10; ++j){
			int col = i * 11 + j + 1;
			for(int c = 0; c <= 9; c++){
				int nxt_mat = nxt[i][c];
				int nxt_rem = (j * 10 + c) % 11;
				int nxt = nxt_mat * 11 + nxt_rem + 1;
				dp.a[nxt][col] = 1;
			}
		}
	}
	dp = mypow(dp, n);
	for(int i = 0; i <= num; ++i) {
		for(int j = 0; j <= 10; ++j) {
			int c = i * 11 + j + 1;
			if(i == num || j == 0)
				ans = (ans + dp.a[c][1]) % mod;
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
        // memset(dp, -1, sizeof(dp));
		solve();
	}
}

F. Fake Math Problem

思路：
设 f ( i ) = ∑ j = 0 i P ( i , j ) f(i) = \sum\limits_{j = 0} ^ {i} P(i, j) f(i)=j=0∑i​P(i,j), 不难发现其对答案的贡献为 f ( i ) − f ( i − a [ i ] − 1 ) ∗ ∏ j = i − a [ i ] i j f(i) - f(i - a[i] - 1) * \prod\limits_{j = i - a[i]}^{i}j f(i)−f(i−a[i]−1)∗j=i−a[i]∏i​j, 模数不是逆元，使用前缀积的话牵扯到除法，需要crt处理，考虑直接用线段树分治维护连乘即可避免处理逆元问题，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

题外话：题解居然是O(1.5e8)的做法，真是shit啊，很难让人理解出题人到底是为了什么才出这题的。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lson p << 1, l, mid
#define rson p << 1 | 1, mid + 1, r
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const int mod =998241383;
const int M = 1e5;
int a[maxn];

struct SegmentTree {
    int sum[maxn << 2];
    void pushUp(int p) {
        sum[p] = (ll) sum[ls] * sum[rs] % mod;
    }
    void build(int p, int l, int r) {
        if (l == r) {
            sum[p] = l;
            return;
        }
        int mid = l + r >> 1;
        build(lson);
        build(rson);
        pushUp(p);
    }
    int query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return sum[p];
        }
        int mid = l + r >> 1;
        int ans = 1;
        if (L <= mid) {
            ans = (ll)ans * query(lson, L, R) % mod;
        }
        if (R > mid) {
            ans = (ll) ans * query(rson, L, R) % mod;
        }
        return ans % mod;
    }
} tr;

int pre[maxn];

int main() {
    int T;
    tr.build(1, 1, M);
    pre[0] = 1;
    for (int i = 1; i <= M; ++i) {
        pre[i] = ((ll) pre[i - 1] * i + 1) % mod;
    }
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i <= n; ++i) {
            cin >> a[i];
        }
        int ans = 0;
        for (int i = 0; i <= n; ++i) {
            if (i == a[i]) {
                ans = (ans + pre[i]) % mod;
            } else {
                ans = (ans + pre[i]) % mod;
                ans = (ans - (ll) tr.query(1, 1, M, i - a[i], i) * pre[i - a[i] - 1] % mod) % mod;
                ans = (ans + mod) % mod;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

G. Good Game, GG

思路：
果然没有队友我完全不会博弈和构造啊， v p vp vp的时候放最后写真机智，最后博了 30 m i n 30min 30min都过不了 140 + 140+ 140+人过的题。

显然当第二个人对2分解的时候，他已经G了，我们考虑每个人的最优策略，对于A，如果是1， 则他的操作比B优1次，对于奇数x，由于2对于B来说是更劣的，所以每次尽量分 x − 2 x - 2 x−2和 2 2 2, 所以A比B多操作 ( x + 1 ) / 2 (x + 1) / 2 (x+1)/2,对于偶数 x , x > 2 x, x>2 x,x>2, 第二个人希望分成任意两个偶数，所以操作次数比A多 x / 2 − 1 x/2 - 1 x/2−1,

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
int a[maxn];

int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll odd = 0, even = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            if (a[i] & 1) {
                odd += (a[i] + 1) / 2;
            } else {
                even += a[i] / 2 - 1;
            }
        }
        if (odd > even) {
            cout << "Alice\n";
        } else {
            cout << "Bob\n";
        }
    }
    return 0;
}

H. History

思路：打表发现边长周期为4，分层图最短路即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using PLI = pair<ll, int>;
using P = pair<int, int>;
const ll INF = 9e18;
int mod;
const int maxn = 2e5 + 5;
int mypow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = (ll)ans * a % mod;
        a = (ll)a * a  % mod;
        b >>= 1;
    }
    return ans;
}
vector<P> G[maxn * 4 + 5];
int main() {
    IOS
    int n, m;
    cin >> n >> m >> mod;
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    auto f = [&](int x) {
        return (ll)(1 + x) * mypow(((1 - x) % mod + mod) %mod, mod - 2) % mod; 
    };
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        for (int j = 0; j < 4; ++j) {
            G[u + j * n].emplace_back(v + (j + 1) % 4 * n, w);
            w = f(w);
        }
    }
    vector<ll> d(n * 4 + 5, INF);
    d[1] = 0;
    q.emplace(d[1], 1);
    while (q.size()) {
        auto [dd, u] = q.top();
        q.pop();
        if (dd > d[u])
            continue;
        for (auto [v, w] : G[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.emplace(d[v], v);
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < 4; ++i) {
        ans = min(ans, d[n + i * n]);
    }
    cout << ans;
    return 0;
}

I. Industrial Nuclear Water

思路：异面判断原理为 f ( x 1 , y 1 , z 1 ) ∗ f ( x 2 , y 2 , z 2 ) < 0 f(x1, y1, z1) * f(x2, y2, z2) < 0 f(x1,y1,z1)∗f(x2,y2,z2)<0，分类讨论6种情况即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
bool check(ll x, ll y, ll z){
    return 1000 * z < x * x + y * y;
}
void solve(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2){
    bool flag = 1;
    if(check(x1, y1, z1) != check(x2, y2, z2))
        flag=0;
	if(check(x1, y1, -z1) != check(x2, y2, -z2))
        flag=0;
	if(check(x1, z1, y1)!=check(x2, z2, y2))
        flag=0;
	if(check(x1, z1, -y1)!=check(x2, z2, -y2))
        flag=0;
	if(check(z1, y1, x1) != check(z2, y2, x2))
        flag=0;
	if(check(z1, y1, -x1)!=check(z2, y2, -x2))
        flag=0;
	cout << (flag ? "Yes\n" : "No\n");
}
int main()
{
    int n;
    cin >> n;
    while(n--) {
        ll x1, y1, z1, x2, y2, z2;
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        bool flag = 1;
        if(check(x1, y1, z1) != check(x2, y2, z2))
            flag=0;
        if(check(x1, y1, -z1) != check(x2, y2, -z2))
            flag=0;
        if(check(x1, z1, y1)!=check(x2, z2, y2))
            flag=0;
        if(check(x1, z1, -y1)!=check(x2, z2, -y2))
            flag=0;
        if(check(z1, y1, x1) != check(z2, y2, x2))
            flag=0;
        if(check(z1, y1, -x1)!=check(z2, y2, -x2))
            flag=0;
        cout << (flag ? "Yes\n" : "No\n");
    }
    return 0;
}

J. Jerry

思路: 最多有 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))这么多的数， b f s bfs bfs即可，时间复杂度 O ( n s q r t ( n ) ) O(nsqrt(n)) O(nsqrt(n))

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn = 1e5 + 5;
const int M = 1e5;
int a[maxn];
bool vis[maxn];

int main() {
    IOS
    int t;
    cin >> t;
    int num = 0;
    for (int i = 1; i * i <= M; ++i)
        a[++num] = i * i;
    queue<int> q;
    vector<int> dis(M + 5, 0);
    q.push(0);
    vis[0] = 1;
    while (q.size()) {
        auto x = q.front();
        q.pop();
        for (int i = 1; i <= num; ++i) {
            if (x + a[i] <= M && !vis[x + a[i]]) {
                vis[x + a[i]] = 1;
                dis[x + a[i]]  = dis[x] + 1;
                q.push(x + a[i]);
            } 
            if (x - a[i] >= 0 && !vis[x - a[i]]) {
                vis[x - a[i]] = 1;
                dis[x - a[i]] = dis[x] + 1;
                q.push(x - a[i]);
            }
        }
    }
    while (t--) {
        int x;
        cin >> x;
        cout << dis[x] << "\n";
    }
    return 0;
}

K. Kera’s line segment

思路：
又是道怪怪题，出题人强制在线想考树套树数据范围又放了二维树状数组过，顺便复习一下树套树，好多年没写过了。
把 ( l , r ) (l, r) (l,r)转化为二维平面上的点，就是个动态二维数点，我们知道静态二维数点可以使用主席树或离线树状数组/ c d q cdq cdq统计，但这题是强制在线，考虑树套树或者是分块。

x x x轴使用任意序列数据结构即可化去一维, y y y轴需要区间取 m i n min min操作，最暴力的办法就是权值线段树套权值线段树。
但观察发现，对于 x x x轴我们只需要前缀信息，即可以树状数组套权值线段树，再观察发现 y y y轴只有后缀询问，可以后缀转前缀，至此，我们只需要支持 x x x轴前缀询问， y y y轴前缀最小值即可，坐标只有 3000 3000 3000, 考虑树状数组套树状数组即可解决该问题。

对于树套树，一般是用来处理偏序问题，我们一般可以在$log ^ d(n) 复杂度内进行一次 复杂度内进行一次 复杂度内进行一次d 维偏序的范围查询， 维偏序的范围查询， 维偏序的范围查询，log^d(n)$的复杂度内进行一次单点修改，例如二维情况下，本质是先利用外层降维，内层支持另一维的操作(一般内存也只够套一层)。

简单介绍一些树套树的应用，如果之后有时间会出一篇博客专门讲偏序问题与可持久化与树套树之间的关系

  • 树状数组套树

    • 优点：常数小，代码短
    • 只能维护基于前缀or支持差分的信息

  • 线段树套树

    • 套平衡树：时间复杂度 O ( l o g 2 n ) O( log^2n ) O(log2n)，空间复杂度 O ( n l o g n ) O( nlogn ) O(nlogn)
    • 套Trie：$时间复杂度O( lognlogv ) ， )， )，空间复杂度O( nlognlogv )$
    • 优点：可以维护很多信息，不用支持差分
    • 缺点：代码shit, 慢，空间大

  • 平衡树套树

    • 套平衡树：时间复杂度 O ( l o g 2 n ) ，空间复杂度 O ( n l o g n ) O( log^2n )，空间复杂度O( nlogn ) O(log2n)，空间复杂度O(nlogn)
    • 套Trie：时间复杂度 O ( l o g n l o g v ) ，空间复杂度 O ( n l o g n l o g v ) O( lognlogv )，空间复杂度O( nlognlogv ) O(lognlogv)，空间复杂度O(nlognlogv)
    • 优点：可以在线支持第一维插入的问题
    • 缺点：代码shit，常数极大，极慢

另外绝大部分问题树套树都可以用分块来解决，分块套树，分块套分块… and so on
虽然一般理论复杂度不够优越，但是常数小加好写啊，还容易debug

像这题就可以用分块套树状数组解决，虽然理论最优为 O ( n s q r t ( n l o g n ) ) O(nsqrt(nlogn)) O(nsqrt(nlogn)), 但比线段树套线段树快多了，还好写
不过说实话，感觉树套树现在挺useless的，一辈子遇不到一次，遇到还不如写分块，还是希望不要陷入写大数据结构题误以为自己很强的错觉才是

二维树状数组写法 200ms

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 3e3 + 10;
const int M = 3000;
struct BIT {
    #define lowb(i) (i & (-i))
    int mx[maxn][maxn], mn[maxn][maxn];
    void add(int x, int y, int val) {
        x = 3001 - x;
        for (int i = x; i <= M; i += lowb(i)) {
            for (int j = y; j <= M; j += lowb(j)) {
                mx[i][j] = max(mx[i][j], val);
                mn[i][j] = min(mn[i][j], val);
            }
        }
    }
    int ask(int x, int y) {
        x = 3001 - x;
        int mxx = 0, mnn = INF;
        for (int i = x; i; i-= lowb(i)) {
            for (int j = y; j; j -= lowb(j)) {
                mnn = min(mnn, mn[i][j]);
                mxx = max(mxx, mx[i][j]);
            }
        }
        return mxx - mnn;
    }
} bit;

int main() {
    IOS
    int n, m;
    cin >> n >> m;
    memset(bit.mn, 0x3f, sizeof(bit.mn));
    for (int i = 1; i <= n; ++i) {
        int l, r, val;
        cin >> l >> r >> val;
        bit.add(l, r, val);
    }
    int last = 0;
    for (int i = 1; i <= m; ++i) {
        int op, l, r, val;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> val;
            l ^= last;
            r ^= last;
            bit.add(l, r, val);
        } else {
            l ^= last;
            r ^= last;
            int ans = bit.ask(l, r);
            cout << ans << '\n';
            last = ans;
        }
    }
    return 0;
}

线段树套线段树 900ms

#include<bits/stdc++.h>
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
using namespace std;
using P = pair<int, int>;
const int INF = 1e9 + 5;
const int maxn = 1e5 + 5;
const int M = 3000;
int rt[maxn << 2], mx[maxn * 200], mn[maxn * 200], lc[maxn * 200], rc[maxn * 200], tot;

void update2(int &p, int l, int r, int x, int val) {
    if (!p) 
        p = ++tot;
    mx[p] = max(mx[p], val);
    mn[p] = min(mn[p], val);
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (x <= mid)
        update2(lson, x, val);
    else
        update2(rson, x, val);
}

void update1(int p, int l, int r, int x, int y, int val) {
    update2(rt[p], 0, M, x, val);
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (y <= mid)
        update1(p << 1, l, mid, x, y, val);
    else
        update1(p << 1 | 1, mid + 1, r, x, y, val);
}

P get(P a, P b) {
    P x = {0, 0};
    x.first = min(a.first, b.first);
    x.second = max(a.second, b.second);
    return x;
}

P query2(int p, int l, int r, int L, int R) {
    if (!p)
        return {INF, -INF};
    if (L <= l && r <= R) {
        return {mn[p], mx[p]};
    }
    int mid = l + r >> 1;
    P ans = {INF, -INF};
    if (L <= mid)
        ans = get(ans, query2(lson, L, R));
    if (R > mid)
        ans = get(ans, query2(rson, L, R));
    return ans;
}

P query(int p, int l, int r, int L1, int R1, int L2, int R2) {
    if (L2 <= l && r <= R2) {
        return query2(rt[p], 0, M, L1, R1);
    }
    int mid = l + r >> 1;
    P ans = {INF, -INF};
    if (L2 <= mid)
        ans = get(ans, query(p << 1, l, mid, L1, R1, L2, R2));
    if (R2 > mid)
        ans = get(ans, query(p << 1 | 1, mid + 1, r, L1, R1, L2, R2));
    return ans;
}

int main() {
    IOS
    fill(mn, mn + maxn * 160 - 1, INF);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        update1(1, 0, M, l, r, x);
    }
    int last = 0;
    for (int i = 1; i <= m; ++i) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            l ^= last;
            r ^= last;
            update1(1, 0, M, l, r, x);
        } else {
            l ^= last;
            r ^= last;
            P ans = query(1, 0, M, l, M, 0, r);
            last = ans.second - ans.first;
            cout << last << '\n';
        }
    }
    return 0;
}

树状数组套线段树 500ms

#include<bits/stdc++.h>
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lson lc[p], l, mid
#define rson rc[p], mid + 1, r
using namespace std;
using P = pair<int, int>;
const int INF = 1e9 + 5;
const int maxn = 1e5 + 5;
const int M = 3000;

struct BIT {
    #define lowb(i) (i & (-i))
    int rt[maxn << 2], mx[maxn * 200], mn[maxn * 200], lc[maxn * 200], rc[maxn * 200], tot;
    void update(int &p, int l, int r, int x, int val) {
        if (!p) 
            p = ++tot;
        mx[p] = max(mx[p], val);
        mn[p] = min(mn[p], val);
        if (l == r)
            return;
        int mid = l + r >> 1;
        if (x <= mid)
            update(lson, x, val);
        else
            update(rson, x, val);
    }
    P get(P a, P b) {
        P x = {0, 0};
        x.first = min(a.first, b.first);
        x.second = max(a.second, b.second);
        return x;
    }
    P query2(int p, int l, int r, int L, int R) {
        if (!p)
            return {INF, -INF};
        if (L <= l && r <= R) {
            return {mn[p], mx[p]};
        }
        int mid = l + r >> 1;
        P ans = {INF, -INF};
        if (L <= mid)
            ans = get(ans, query2(lson, L, R));
        if (R > mid)
            ans = get(ans, query2(rson, L, R));
        return ans;
    }
    void add(int x, int y, int val) {
        for (int i = y; i <= M; i += lowb(i)) {
            update(rt[i], 0, M, x, val);
        }
    }
    P ask(int x, int y) {
        P ans = {INF, -INF};
        for (int i = y; i; i -= lowb(i)) {
            ans = get(ans, query2(rt[i], 0, M, x, M));
        }
        return ans;
    }
} bit;

int main() {
    IOS
    fill(bit.mn, bit.mn + maxn * 160 - 1, INF);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        bit.add(l, r, x);
        // update1(1, 0, M, l, r, x);
    }
    int last = 0;
    for (int i = 1; i <= m; ++i) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            l ^= last;
            r ^= last;
            bit.add(l, r, x);
            // update1(1, 0, M, l, r, x);
        } else {
            l ^= last;
            r ^= last;
            P ans = bit.ask(l, r);
            // P ans = query(1, 0, M, l, M, 0, r);
            last = ans.second - ans.first;
            cout << last << '\n';
        }
    }
    return 0;
}

L. League of Legends

思路：
枚举算出答案为3.5

print(3.5)

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/17526.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

PS磨皮插件portraiture最新版磨皮工具

PS磨皮插件portraiture最新版磨皮工具

Portraiture是一款智能磨皮插件&#xff0c;为Photoshop和Lightroom添加一键磨皮美化功能&#xff0c;快速对照片中皮肤、头发、眉毛等部位进行美化&#xff0c;无需手动调整&#xff0c;大大提高P图效率。全新4版本&#xff0c;升级AI算法&#xff0c;并独家支持多人及全身模式…
阅读更多...
I2C工作流程

I2C工作流程

FM33A0XX的I2C接口只用作主机&#xff0c;且不支持多主机&#xff0c;因此挂在总线上的其他设备都是从机。总线上总是由主机提供同步时钟SCL&#xff0c;SDA数据流方向可以是主机发送从机接收&#xff0c;或者从机发送主机接收。 数据发送流程 1、主机发起 START 时序 2、主机…
阅读更多...
C++之基础总结

C++之基础总结

目录 POD类型左值和右值静态全局变量(static)类型转换const/constexprconstconstexpr C中的关键字union基础知识点编译与函数参数入栈总结一些常见用法归纳&#xff1a; POD类型 平凡的和标准布局的——貌似和深度探索C对象模型中关于按位拷贝冲突 平凡的定义&#xff1a;符合…
阅读更多...
Camtasia2023最好用的电脑屏幕录制软件

Camtasia2023最好用的电脑屏幕录制软件

Camtasia2023是市场上最好的录像机和屏幕录制软件之一。强大的软件视频编辑程序的Camtasia 适用于Windows和iOS。 它支持多种流行的媒体格式&#xff0c;并对您创建的视频提供令人印象深刻的控制范围。3000多万专业人士在全球范围内使用Camtasia展示产品&#xff0c;教授课程&a…
阅读更多...
文字的显示

文字的显示

文字的显示 文章目录 文字的显示1.文字编码方式2.英文和汉字的点阵显示3.显示中文“中”和“A”show_font.c结果 1.文字编码方式 数字>代表什么->显示为什么 GBK国标拓展 下列代码用不同编码方式保存utf-8.c ansi.c #include <stdio.h>int main(int argc ,char *…
阅读更多...
网络编程之 Socket 套接字（使用数据报套接字和流套接字分别实现一个小程序（附源码））

网络编程之 Socket 套接字（使用数据报套接字和流套接字分别实现一个小程序（附源码））

文章目录 1. 什么是网络编程2. 网络编程中的基本概念1&#xff09;发送端和接收端2&#xff09;请求和响应3&#xff09;客户端和服务端4&#xff09;常见的客户端服务端模型 3. Socket 套接字1&#xff09;Socket 的分类2&#xff09;Java 数据报套接字通信模型3&#xff09;J…
阅读更多...
基于Open3D的点云处理2-Open3D的IO与数据转换

基于Open3D的点云处理2-Open3D的IO与数据转换

三维数据类型 点云 某个坐标系下的点数据集&#xff0c;每个点包括三维坐标X&#xff0c;Y&#xff0c;Z、颜色、分类值、强度值、时间等信息&#xff1b; 储存格式&#xff1a;pts、LAS、PCD、xyz、asc、ply等&#xff1b;Mesh 多边形网格&#xff0c;常见的是三角网格&#…
阅读更多...
有研究员公开了一个解析并提取 Dell PFS BIOS 固件的工具（上）

有研究员公开了一个解析并提取 Dell PFS BIOS 固件的工具（上）

导语&#xff1a;研究员公开了一个解析并提取 Dell PFS BIOS 固件的工具。 Dell PFS BIOS提取器 介绍 解析 Dell PFS BIOS 映像并提取其 SPI/BIOS/UEFI 固件组件。它支持所有Dell PFS 修订版和格式&#xff0c;包括最初在 ThinOS 包中LZMA压缩、ZLIB压缩或拆分成块的格式。输出…
阅读更多...
Kafka上的优化经验

Kafka上的优化经验

1. 平滑扩容 Motivation kafka扩容⼀台新机器的流程 假如集群有 3 个 broker &#xff0c;⼀共有 4 个 TP &#xff0c;每个 3 副本&#xff0c;均匀分布。现在要扩容⼀台机器&#xff0c; 新 broker 加⼊集群后需要通过⼯具进⾏ TP 的迁移。⼀共迁移 3 个 TP 的副…
阅读更多...
Spring Boot集成ShardingSphere实现按月数据分片及创建自定义分片算法 | Spring Cloud 44

Spring Boot集成ShardingSphere实现按月数据分片及创建自定义分片算法 | Spring Cloud 44

一、前言 在前面我们通过以下章节对数据分片有了基础的了解&#xff1a; Spring Boot集成ShardingSphere实现数据分片&#xff08;一&#xff09; | Spring Cloud 40 Spring Boot集成ShardingSphere实现数据分片&#xff08;二&#xff09; | Spring Cloud 41 Spring Boot集…
阅读更多...
权限提升：信息收集 .（Linux系统）

权限提升：信息收集 .（Linux系统）

权限提升&#xff1a;信息收集. 权限提升简称提权&#xff0c;由于操作系统都是多用户操作系统&#xff0c;用户之间都有权限控制&#xff0c;比如通过 Web 漏洞拿到的是 Web 进程的权限&#xff0c;往往 Web 服务都是以一个权限很低的账号启动的&#xff0c;因此通过 Webshel…
阅读更多...
1.1 基于B/S 结构的 Web 应用

1.1 基于B/S 结构的 Web 应用

文章目录 1.1 基于B/S 结构的 Web 应用1.2 JDK安装与配置1.3 服务器Tomcat下载与安装1.4 Eclipse安装与使用1.4.1 Eclipse 下载及创建Dynamic Web Project1.4.2 Eclipse 中的编码问题1.4.3 将Tomcat和Eclipse相关联1.4.4 Eclipse 自动部署项目到 Tomcat 的 webapps 目录 1.5 My…
阅读更多...
【AWS入门】AWS Lamda

【AWS入门】AWS Lamda

目录 创建一个Lamda函数用Lamda函数控制启停EC2实例创建一台EC2实例创建角色创建lamda函数 使用Amazon EventBridge计划启停实例创建EventBridge 用户往S3存储桶上传图片文件&#xff0c;触发Lambda函数&#xff0c;将图片压缩并上传至另一个存储桶创建两个存储桶通过Cloudform…
阅读更多...
【SpringMVC】| SpringMVC执行流程原理 | 常用注解 剥析

【SpringMVC】| SpringMVC执行流程原理 | 常用注解 剥析

MVC目录 一. &#x1f981; MVC模型二. &#x1f981; SpringMVC1. SpringMVC执行流程&#xff08;重点&#xff09;Ⅰ. SpringMVC四大组件Ⅱ. 执行流程 2. RequestMapping3. RequestParam4. ReuqestHeader & CookieValue5. RESTful风格支持Ⅰ. 传统 vs restfulⅡ. PathVar…
阅读更多...
【网络技术】什么是CNI

【网络技术】什么是CNI

序言 你只管努力&#xff0c;其他交给时间&#xff0c;时间会证明一切。 Never look back unless you are planning to go that way. 文章标记颜色说明&#xff1a; 黄色&#xff1a;重要标题红色&#xff1a;用来标记结论绿色&#xff1a;用来标记一级论点蓝色&#xff1a;用…
阅读更多...
【应急响应】日志自动提取分析项目ELKLogkitLogonTracerAnolog等

【应急响应】日志自动提取分析项目ELKLogkitLogonTracerAnolog等

日志自动提取-七牛Logkit&观星应急工具 1、七牛Logkit&#xff1a;(Windows&Linux&Mac等) https://github.com/qiniu/logkit/ 支持的数据源&#xff08;各类日志&#xff0c;各个系统&#xff0c;各个应用等&#xff09; File: 读取文件中的日志数据&#xff0c;包…
阅读更多...
面了一个4年经验的测试工程师，自动化都不会也要15k，我也是醉了····

面了一个4年经验的测试工程师，自动化都不会也要15k，我也是醉了····

在深圳这家金融公司也待了几年&#xff0c;被别人面试过也面试过别人&#xff0c;大大小小的事情也见识不少&#xff0c;今天又是团面的一天&#xff0c; 一百多个人都聚集在一起&#xff0c;因为公司最近在谈项目出来面试就2个人&#xff0c;无奈又被叫到面试房间。 整个过程…
阅读更多...
数说热点 | 跟着《长月烬明》起飞，今年各地文旅主打的就是一个听劝

数说热点 | 跟着《长月烬明》起飞，今年各地文旅主打的就是一个听劝

近日&#xff0c;随着热播剧《长月烬明》的爆火&#xff0c;蚌埠、宣城、敦煌等多个与剧情梦幻联动的宝藏城市被带飞&#xff0c;各地热心网友也纷纷催促自家文旅局赶紧“蹭飞”&#xff0c;《长月烬明》以一己之力打造了影视文旅融合的新样板。 仙偶剧特效天花板&#xff0c;…
阅读更多...
《互联网安全产品漏洞管理规定》

《互联网安全产品漏洞管理规定》

《网络产品安全漏洞管理规定》由工业和信息化部、国家互联网信息办公室、公安部联合印发&#xff0c;自2021年9月1日起施行。 该《规定》明确&#xff0c;任何组织或者个人不得利用网络产品安全漏洞从事危害网络安全的活动&#xff0c;不得非法收集、出售、发布网络产品安全漏洞…
阅读更多...
Redis高频面试题，使用场景

Redis高频面试题，使用场景

一、缓存 1、什么是缓存穿透 ? 怎么解决 ? 缓存穿透 查询一个不存在的数据&#xff0c;mysql查询不到数据也不会直接写入缓存&#xff0c;就会导致每次请求都查数据库。 解决 方案一&#xff1a;缓存空数据&#xff0c;查询返回的数据为空&#xff0c;仍把这个空结果进行…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发