暑假牛客多校第九场 2023-8-15（D、I）

dkdklcx / 2023-08-17 / 原文

未补完

D. Non-Puzzle: Error Permutation

算法：差分

做法：
考虑题目的数据，我们的做法可以先枚举出不合法的区间数，然后由区间总数减去不合法区间数。我们首先确定一个数，令这个数就是包含这个数的一段区间的不和法值，即这个数是第 \(i\) 小的数。一开始我们使这段区间大小为 \(1\)，里面的数即为我们要确定的数。随后右边界向右移，找到第一个使这个区间中我们所确定的数是不和法的位置，然后右边界继续右移，直到使得这个区间中我们所确定的数是最后一个不合法的，这段不合法区间都要加起来。接着左边界左移，那么我们所确定的数变成了第 \(i - l + 1\) 个数，但是我们所确定的数不一定是第 \(i - l + 1\) 小的数，所以要继续右移边界，而且右移的边界是和上一次右边界结束的位置是一样的，因为上一次右边界确定的是我们所确定的数是第 \(i - (l - 1) + 1\)，现在变成了这个数必须是第 \(i - l + 1\) 小，那么右边界就必须向右移来找比我们确定的数还要小的数使我们目前的数的排名加一（如果新加的左边界的数比我们确定的数大的话，我们就需要右移边界找比我们确定的数更小的数来使排名加一。如果新加的数比我们所确定的数还要小，那么我们所确定的数就是第 \(i - l + 1\) 小）。我们算不合法区间可能有重复，所以用差分维护。

code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
typedef pair<int, string> PIS;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 5010, M = 100100, INF = 0x3f3f3f3f, mod = 998244353, TIME = 50001;

int n;
int w[N];
int g[N][N];

void add(int p, int rst, int red)
{
    g[p][rst] += 1, g[p][red + 1] -= 1;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> w[i];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            g[i][j] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int l = i, rst = i, red = i, cnt = 0; l >= 1; l--)
        {
            if (w[l] <= w[i])cnt++;
            while (cnt < i - l + 1 && red < n)
            {
                red++,  rst = red;
                if(w[red] < w[i])cnt++;
            }
            if (cnt == i - l + 1)
            {
                while (red < n && w[red + 1] > w[i])red++;
                add(l, rst, red);
            }
        }
    }

    LL ans = 0;
    for(int i = 1; i <= n ; i++)
        for (int j = 1; j <= n; j++)
        {
            g[i][j] += g[i][j - 1];
            if (i <= j && !g[i][j])ans++;
        }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

I. Non-Puzzle: Segment Pair

算法：排序

做法：我们定义一个数组 \(b\)，\(b[0]\) 表示未覆盖这个点的区间个数，\(b[1]\) 表示一对区间只有一个区间覆盖这个点的区间个数，\(b[2]\) 表示一对区间两者都覆盖这个点的区间个数。我们再定义一个数组 \(a\)，\(a[i]\) 表示编号为 \(i\) 的一对区间在数组 \(b\) 中的状态，那么 \(a[i]\) 的值就有0,1,2三种情况。由于我们考虑的是每个点的区间覆盖情况，因此必定有重复的情况出现，那么我们就按照一遇到区间的左边界我们就计算这个区间加入后的区间覆盖方案数。由于每一次都是在区间一加入后就计算方案数，这是不重不漏的。另外，每次遍历区间时我们会删去之前区间在数组 \(b\) 的状态，更新这个区间的状态和在数组 \(b\) 的状态。(看代码就懂了)

code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 500100, M = 100100, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n;
int p[N], a[N], b[4];

struct Node
{
    int x, v, id;
};

bool cmp(Node i, Node j)
{
    if (i.x != j.x)return i.x < j.x;
    return i.v < j.v;
}

void solve()
{
    cin >> n;
    p[0] = 1, b[0] = n;
    vector<Node> ve;
    for (int i = 1; i <= n; i++)p[i] = (LL)p[i - 1] * 2 % mod;
    for (int i = 0; i < n; i++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        ve.push_back({ l1, 1, i });
        ve.push_back({ r1 + 1, -1, i });
        ve.push_back({ l2, 1, i });
        ve.push_back({ r2 + 1, -1, i });
    }

    sort(ve.begin(), ve.end(), cmp);
    LL ans = 0;
    for (auto t : ve)
    {
        b[a[t.id]]--;
        a[t.id] += t.v;
        if (t.v == 1 && b[0] == 0)
            ans = (ans + p[b[2]]) % mod;
        b[a[t.id]]++;
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}