区间和问题 - 前缀和

最大子段和

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[212345];
int sum[212345];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	int pos = 0;//sum[0] 
	int ans = a[1];
	for(int r=1;r<=n;r++){
		//sum[pos] : sum[0]~sum[r-1] 的最小值 
		ans=max(ans,sum[r] - sum[pos]);
		if(sum[r] < sum[pos])
			pos = r;
	}
	cout<<ans<<"\n";
	return 0;
}

【CSGRound2】光骓者的荣耀

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, k, sum[1000005], a[1000005], maxn = 0;
;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    n--;
    if (k < 0)
        k = -k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i + k - 1 <= n; i++)
    {
        if (sum[i + k - 1] - sum[i - 1] > maxn)
        {
            maxn = sum[i + k - 1] - sum[i - 1];
        }
    }
    cout << sum[n] - maxn << endl;

    return 0;
}

最大加权矩形

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120 + 5;
int n;
int a[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            a[i][j] += a[i][j - 1];
        for (int j = 1; j <= n; j++)
            a[i][j] += a[i - 1][j];
    }
    int ans = a[1][1];
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++)
            for (int xx = 1; xx <= x; xx++)
                for (int yy = 1; yy <= y; yy++)
                    ans = max(ans, a[x][y] - a[x][yy - 1] - a[xx - 1][y] + a[xx - 1][yy - 1]);
    cout << ans << endl;
    return 0;
}

领地选择

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m, c;
ll a[1005][1005];
ll sum[1005][1005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            sum[i][j] = sum[i][j - 1] + a[i][j];
        }
        for (int j = 1; j <= m; j++)
        {
            sum[i][j] += sum[i - 1][j];
        }
    }
    long long ans=sum[c][c], ansi=1, ansj=1;
    for (int i = 1; i + c - 1 <= n; i++)
    {
        for (int j = 1; j + c - 1 <= m; j++)
        {
            if (sum[i + c - 1][j + c - 1] - sum[i + c - 1][j - 1] - sum[i - 1][j + c - 1] + sum[i - 1][j - 1] > ans)
            {
                ans = sum[i + c - 1][j + c - 1] - sum[i + c - 1][j - 1] - sum[i - 1][j + c - 1] + sum[i - 1][j - 1];
                ansi = i;
                ansj = j;
            }
        }
    }
    cout << ansi << " " << ansj << endl;
    return 0;
}

RMQ问题 - ST表

【模板】ST 表

#include <bits/stdc++.h>
using namespace std;
int n, m;  // n个数 m组询问
int a[100000 + 10];
// f[i][j]表示从a[i]开始 2^j 个元素的最值
int f[100000 + 10][32];
int main() {
	cin >> n >> m; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i][0] = a[i];
    }
    //预处理 f 数组
    // 1<<j : 2^j 
    int logn = log2(n);
    for (int j = 1; j <= logn; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    //处理询问
    for (int i = 1; i <= m; i++) {
        int p, q;
        cin >> p >> q; 
        int logx = log2(q - p + 1);
        cout << max(f[p][logx], f[q - (1 << logx) + 1][logx])) << "\n";
    }
    return 0;
}

• 【选做】

区间修改 - 差分

语文成绩

#include <bits/stdc++.h>
using namespace std;
int n, p;
int a[5123456];
int d[5123456];
int main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        d[i] = a[i] - a[i - 1];
    while (p--)
    {
        int l, r, x;
        cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }
    int ans = d[1];
    a[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1] + d[i];
        ans = min(ans, a[i]);
    }
    cout << ans << "\n";
    return 0;
}

海底高铁

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m, p[100005], a[100005], b[100005], c[100005];
ll d[100005], cnt[100005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < m; i++)
    {
        if (a[i] <= a[i + 1])
        {
            d[a[i]]++;
            d[a[i + 1]]--;
        }
        else
        {
            d[a[i + 1]]++;
            d[a[i]]--;
        }
    }
    for (int i = 1; i <= n - 1; i++)
    {
        cnt[i] = cnt[i - 1] + d[i];
    }
    ll ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        ans += min(a[i] * cnt[i], b[i] * cnt[i] + c[i]);
    }
    cout << ans << endl;
    return 0;
}

三步必杀

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m, l, r, s, e, d, a[10000000], maxx, sumans, sum1, sum2;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> l >> r >> s >> e;
        d = (e - s) / (r - l);
        a[l] += s;
        a[l + 1] += d - s;
        a[r + 1] -= d + e;
        a[r + 2] += e;
    }
    sumans = 0;
    maxx = 0;
    sum1 = 0;
    sum2 = 0;
    for (int i = 1; i <= n; i++)
    {
        sum1 += a[i];
        sum2 += sum1;
        maxx = max(maxx, sum2);
        sumans ^= sum2;
    }
    cout<<sumans<<" "<<maxx<<endl;

    return 0;
}

单调队列 - 滑动窗口最值

滑动窗口 /【模板】单调队列

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1123456];
deque<int> q; //存下标i，a[i]单调
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    //最小值
    for (int i = 1; i < k; i++)
    {
        while (!q.empty() && a[q.back()] >= a[i])
            q.pop_back();
        q.push_back(i);
    }
    for (int i = k; i <= n; i++)
    {
        while (!q.empty() && a[q.back()] >= a[i])
            q.pop_back();
        q.push_back(i);
        while (!q.empty() && i - q.front() >= k)
            q.pop_front();
        cout << a[q.front()] << " ";
    }
    cout << "\n";
    //最大值
    while (!q.empty())
        q.pop_back();
    for (int i = 1; i < k; i++)
    {
        while (!q.empty() && a[q.back()] <= a[i])
            q.pop_back();
        q.push_back(i);
    }
    for (int i = k; i <= n; i++)
    {
        while (!q.empty() && a[q.back()] <= a[i])
            q.pop_back();
        q.push_back(i);
        while (!q.empty() && i - q.front() >= k)
            q.pop_front();
        cout << a[q.front()] << " ";
    }
    cout << "\n";

    return 0;
}

单调栈 - 每个数后面第一个比它大/小的元素

发射站

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, h[1000005], v[1000005], sum[1000005], ans;
stack<int> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i] >> v[i];
        sum[i] = 0;
    }
    while (s.size())
        s.pop();
    for (int i = 1; i <= n; i++)
    {
        while (s.size() && h[i] > h[s.top()])
        {
            sum[i] += v[s.top()];
            s.pop();
        }
        s.push(i);
    }
    ans = 0;
    while (s.size())
        s.pop();
    for (int i = n; i >= 1; i--)
    {
        while (s.size() && h[i] > h[s.top()])
        {
            sum[i] += v[s.top()];
            s.pop();
        }
        s.push(i);
        if (sum[i] > ans)
        {
            ans = sum[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Patrik 音乐会的等待

#include <bits/stdc++.h>
using namespace std;
int n;
struct Person
{
    int val, cnt;
};
stack<Person> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        Person now = (Person){x, 1};
        while (!s.empty() && s.top().val <= x)
        {
            ans += s.top().cnt;
            if (s.top().val == x)
                now.cnt += s.top().cnt;
            s.pop();
        }
        if (!s.empty())
            ans++;
        s.push(now);
    }
    cout << ans << endl;
    return 0;
}

双指针

A-B 数对

#include <bits/stdc++.h>
using namespace std;
int n, C;
int a[212345];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> C;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    long long ans = 0;
    int l = 1; //第一个大于等于 a[i]+C 的位置
    int r = 1; //第一个大于 a[i]+C 的位置
    for (int i = 1; i <= n; i++)
    {
        while (l <= n && !(a[l] >= a[i] + C))
            l++;
        while (r <= n && !(a[r] > a[i] + C))
            r++;
        ans += r - l;
    }
    cout << ans << "\n";
    return 0;
}

[USACO16OPEN] Diamond Collector S

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[51234];
int f[51234];    // f[i]:选择了 a[i]，并且 a[i] 是当前货架上最大值时 最多能选取几个钻石。
int g[51234];    // f[i]:选择了 a[i]，并且 a[i] 是当前货架上最小值时 最多能选取几个钻石。
int gMax[51234]; // gMax[i]:g[i]~g[n]的最大值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    //随着一个指针p往一个方向单调移动，另一个指针q也是单调移动的
    //那么q就可以从之前的q的位置来挪动，而不需要从头开始挪动
    //预处理 f[i]
    //与a[i]差值在k以内的，最左边的位置是 j
    for (int i = 1, j = 1; i <= n; i++)
    {
        //维护好 j 的位置
        while (a[i] - a[j] > k)
            j++;
        f[i] = i - j + 1; // [j,i] 都是满足差值要求的
    }
    //预处理 g[i]
    //与a[i]差值在k以内的，最右边的位置是 j
    for (int i = 1, j = 1; i <= n; i++)
    {
        //维护好 j 的位置
        while (j + 1 <= n && a[j + 1] - a[i] <= k)
            j++;
        g[i] = j - i + 1; // [i,j] 都是满足差值要求的
    }
    //预处理gMax[i]: g[i]~g[n]的最大值
    gMax[n] = g[n];
    for (int i = n - 1; i >= 1; i--)
        gMax[i] = max(gMax[i + 1], g[i]);

    //枚举左边货架选取了的最大的钻石，找到右边最多选取几个
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int left, right;
        left = f[i];
        if (i == n)
            right = 0;
        else
            right = gMax[i + 1];
        ans = max(ans, left + right);
    }
    cout << ans << "\n";
    return 0;
}

逛画展

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1123456];
int cnt[2123];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int now = 1;
    cnt[a[1]]++;
    int minx = n;
    int mini = 1;
    for (int i = 1, j = 1; i <= n; i++)
    {
        while (j < n && now != m)
        {
            j++;
            cnt[a[j]]++;
            if (cnt[a[j]] == 1)
                now++;
        }
        if (now == m && j - i + 1 < minx)
        {
            minx = j - i + 1;
            mini = i;
        }
        cnt[a[i]]--;
        if (cnt[a[i]] == 0)
            now--;
    }
    cout << mini << " " << mini + minx - 1 << endl;
    return 0;
}

CF1304C Air Conditioner 调整温度

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct Node
{
    ll t, l, r;
} a[105];
bool cmp(const Node &a, const Node &b)
{
    return a.t < b.t;
}
ll T, n, m, L, R;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].t >> a[i].l >> a[i].r;
        }
        sort(a + 1, a + n + 1, cmp);
        a[0].t = 0;
        L = R = m;
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            L -= a[i].t - a[i - 1].t;
            R += a[i].t - a[i - 1].t;
            if (a[i].r < L || R < a[i].l)
            {
                flag = false;
                break;
            }
            L = max(L, a[i].l);
            R = min(R, a[i].r);
        }
        if (flag)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

CF1251C Minimize The Integer 只能交换奇偶不同的相邻数位求最小值

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int t;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> s;
        int o, e;
        o = e = 0;
        while (o < s.length() && s[o] % 2 != 1)
            o++;
        while (e < s.length() && s[e] % 2 != 0)
            e++;
        while (o < s.length() && e < s.length())
        {
            if (s[o] < s[e])
            {
                cout << s[o++];
                while (o < s.length() && s[o] % 2 != 1)
                    o++;
            }
            else
            {
                cout << s[e++];
                while (e < s.length() && s[e] % 2 != 0)
                    e++;
            }
        }
        while (o < s.length())
        {
            cout << s[o++];
            while (o < s.length() && s[o] % 2 != 1)
                o++;
        }
        while (e < s.length())
        {
            cout << s[e++];
            while (e < s.length() && s[e] % 2 != 0)
                e++;
        }
        cout << endl;
    }
    return 0;
}

CF231C To Add or Not to Add k次+1让某个数出现次数最多

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, k, a[100005], sum, maxx, maxn;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    maxn = 0;
    cin >> n >> k;
    for (int i = 1, j = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1, j = 1; i <= n; i++)
    {
        sum += a[i];
        while ((i - j + 1) * a[i] - sum > k)
            sum -= a[j++];
        if (i - j + 1 > maxn)
        {
            maxn = i - j + 1;
            maxx = a[i];
        }
    }
    cout << maxn << " " << maxx << endl;
    return 0;
}

【选做】CF1198A CF939E