比赛记录【Educational Codeforces Round 92】

He_Ren · 2020-08-07 21:02:19 · 个人记录

Educational Codeforces Round 92

E. Calendar Ambiguity

考虑将所有天数编号，那么第 x 个月的第 y 天的编号就是 (x-1) \times d + y。那么第 x 个月的第 y 天和第 y 个月的第 x 天的星期数相同，当且仅当 (x-1)\times d + y \equiv (y-1) \times d + x \pmod w。

化简一下，(d-1)x \equiv (d-1)y \pmod w，其中，1\leq x,y\leq \min(m,d)。

设 p = \gcd(w, d-1)，容易发现，上式等价于 px \equiv py\pmod w。

发现上面的条件满足当且仅当 x \equiv y\pmod{(w/p)}。

My Code

我在数论方面的知识还比较薄弱。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int gcd(int a,int b){ return b? gcd(b,a%b): a;}

void solve(void)
{
    int m,d,w;
    scanf("%d%d%d",&m,&d,&w);
    ll mx = min(m,d);

    --d;
    d = gcd(d,w);

    ll ans = 0;

    ll tot = mx / (w/d);
    ll rem = mx % (w/d);

    ans += rem * ((tot+1) * tot / 2);
    ans += (w/d - rem) * ((tot-1) * tot / 2);

    printf("%lld\n",ans);
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

Code

ecnerwala

#include<bits/stdc++.h>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int64_t M, D, W; cin >> M >> D >> W;
        M = min(M, D);
        W /= gcd(W, D-1);
        cout << W * (M / W) * (M/W - 1) / 2 + (M%W) * (M/W) << '\n';
    }

    return 0;
}

Um_nik

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}

void solve() {
    ll m, d, w;
    scanf("%lld%lld%lld", &m, &d, &w);
    m = min(m, d);
    w /= gcd(w, d - 1);
    ll k = m / w;
    ll ans = m * k - w * (k * (k + 1) / 2);
    printf("%lld\n", ans);
}

int main()
{
    startTime = clock();
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    int t;
    scanf("%d", &t);
    while(t--) solve();

    return 0;
}

neal

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

int64_t choose2(int64_t n) {
    return n * (n - 1) / 2;
}

void run_case() {
    int64_t M, D, W;
    cin >> M >> D >> W;
    int64_t G = __gcd(D - 1, W);
    int64_t mod = W / G;
    int64_t N = min(M, D);
    int64_t answer = (N % mod) * choose2(N / mod + 1) + (mod - N % mod) * choose2(N / mod);
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int tests;
    cin >> tests;

    while (tests-- > 0)
        run_case();
}

icecuber

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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    ll m, d, w;
    cin >> m >> d >> w;
    w /= gcd(d-1,w);
    //if (m > 1e4) break;

    /*int ans = 0;
    for (int y = 0; y < min(m,d); y++) {
      ans += y/w;
      }*/
    m = min(m,d);
    ll ans = (m/w)*(m/w-1)/2*w+(m/w)*(m%w);
    cout << ans << endl;
  }
}

natsugiri

#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
LL gcd(LL x, LL y) {
    while (1) {
    if (x) y %= x; else return y;
    if (y) x %= y; else return x;
    }
}

LL M, D, W;

void MAIN() {
    scanf("%lld%lld%lld", &M, &D, &W);
    // 0 <= x < y < min(M, D);
    // (x * D + y) % W == (y * D + x) % W;

    // 0 <= x < y < min(M, D);
    // y = x + k;
    // k % W == kD % W;
    // k(D - 1) == 0;

    LL ans = 0;
    if (M == 1 || D == 1) {
    ans = 0;
    } else {
    LL g = gcd(W, D-1);
    LL step = W / g;
    LL LIMIT = min(M, D) - 1;
    LL B = LIMIT / step;
    ans += B * (B-1) / 2 * step;
    ans += B * (LIMIT - B * step + 1);

    //for (LL x=1; x<=LIMIT; x++) {
    //    ans += x / step;
    //}
    }

    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

F. Bicolored Segments

考虑将所有线段按右端点从小到大排序，右端点相同的按左端点从小到大排序，这样可以保证对于一条线段，它包含的线段都排在它左侧。

考虑 dp。先将坐标离散化，f_k(i) 表示将坐标 i+1 及以后都选择第 k 种颜色，且没有线段横跨 i 到 i+1 的最大答案。那么对于一条颜色为 t 的线段 l,r，只需要先将所有的 f_k(x)\ (x<l) 加一，然后查询 f_k(x)\ (x<l) 的最大值即可。然后，用这条线段的答案更新 f_{\neg k}(r) 即可（\neg k 表示与 k 相反的颜色）。可以用线段树实现，支持区间加，区间查询最大值。

My Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;
const int MAXP = MAXN<<1;
const int inf = 0x3f3f3f3f;

struct Segment_Tree
{
    int mx[MAXP<<2], tag[MAXP<<2];
    #define ls(u) ((u)<<1)
    #define rs(u) ((u)<<1|1)
    #define lson(u) ls(u),l,mid
    #define rson(u) rs(u),mid+1,r
    inline void push_up(int u){ mx[u]=max(mx[ls(u)], mx[rs(u)]);}
    inline void push_down(int u)
    {
        mx[ls(u)]+=tag[u]; tag[ls(u)]+=tag[u];
        mx[rs(u)]+=tag[u]; tag[rs(u)]+=tag[u];
        tag[u]=0;
    }

    inline void update(int u,int l,int r,int ql,int qr,int k)
    {
        if(ql<=l&&r<=qr){ mx[u]+=k; tag[u]+=k; return;}
        push_down(u);
        int mid=(l+r)>>1;
        if(ql<=mid) update(lson(u),ql,qr,k);
        if(mid<qr) update(rson(u),ql,qr,k);
        push_up(u);
    }
    inline int query(int u,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr) return mx[u];
        push_down(u);
        int mid=(l+r)>>1, res=0;
        if(ql<=mid) res=max(res, query(lson(u), ql,qr));
        if(mid<qr) res=max(res, query(rson(u), ql,qr));
        push_up(u);
        return res;
    }
}tree[2];

struct Seg
{
    int l,r, t;
}a[MAXN];
inline bool cmp(const Seg &p,const Seg &q){ return p.r==q.r? p.l>q.l: p.r<q.r;}

int f[MAXN];

int dsc[MAXN<<1], dcnt=0;
int g[2][MAXP];

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].t),
        --a[i].t;

    dsc[++dcnt] = -inf;
    for(int i=1; i<=n; ++i)
        dsc[++dcnt] = a[i].l,
        dsc[++dcnt] = a[i].r;
    sort(dsc+1,dsc+dcnt+1);
    dcnt = unique(dsc+1,dsc+dcnt+1)-dsc-1;
    for(int i=1; i<=n; ++i)
        a[i].l = lower_bound(dsc+1,dsc+dcnt+1,a[i].l) - dsc,
        a[i].r = lower_bound(dsc+1,dsc+dcnt+1,a[i].r) - dsc;

    sort(a+1,a+n+1,cmp);

    int ans = 0;
    for(int i=1; i<=n; ++i)
    {
        tree[!a[i].t].update(1,1,dcnt, 1,a[i].l-1, 1);

        f[i] = tree[!a[i].t].query(1,1,dcnt, 1,a[i].l-1);
        if(f[i] > g[a[i].t][a[i].r])
            tree[a[i].t].update(1,1,dcnt, a[i].r,a[i].r, f[i] - g[a[i].t][a[i].r]),
            g[a[i].t][a[i].r] = f[i];

        ans = max(ans, f[i]);
    }
    printf("%d",ans);
    return 0;
}

Code

ecnerwala

将两种颜色的线段抽象成点，把不可同时选择的关系表示成边，那么问题转化成了二分图的最大独立集问题。一个定理是，二分图的最大独立集，等于总点数减去它的最大匹配，下面我们会用到这个定理。

将所有线段按左端点从小到大排序。维护两个小根堆，维护当前两种颜色线段的右端点。每次考虑到当前线段，我们就把堆中所有与它不相交的线段弹出，进行下文的计算后，将此线段压入对应的堆中。注意因为这一步，我们可以保证任意时刻，两个堆中的所有线段两两相交。下面考虑弹出的这些线段。

设红线段有 x 个，蓝线段有 y 个，不妨假设 x\leq y。注意这些线段两两相交，所以考虑当前线段的话，其最大匹配的大小是 x。考虑剩下的 y-x 个线段如何匹配。设储存红线段的堆，在弹出 x 条线段后的大小为 size，那么剩余 y-x 条蓝线段可以和剩下的 size 条红线段进行匹配，这一步可以产生 \min(y-x, size) 个匹配，于是进行匹配，并把储存红色线段的堆弹出 \min(y-x,size) 次。那么这些线段产生的最大独立集大小就是 y + x + \min(y-x,size) - x - \min(y-x,size) = y。容易证明算法的正确性。

这种做法代码的长度很小，但是不太容易想到。考场上首先想到正确，但码量较高的做法的话，不要过多考虑码量的问题。考场上非要考虑简便做法的话，不但会浪费时间，而且可能使程序出现错误。

#include<bits/stdc++.h>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int N; cin >> N;
    struct seg {
        int l, r;
        bool t;
    };
    vector<seg> S(N);
    for (auto& s : S) {
        cin >> s.l >> s.r;
        int t; cin >> t;
        s.t = t-1;
    }
    vector<int> coords(N);
    for (int i = 0; i < N; i++) {
        coords[i] = S[i].l;
    }
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());

    for (auto& s : S) {
        s.l = int(lower_bound(coords.begin(), coords.end(), s.l) - coords.begin());
        s.r = int(upper_bound(coords.begin(), coords.end(), s.r) - coords.begin());
    }
    sort(S.begin(), S.end(), [&](const seg& a, const seg& b) { return a.l < b.l; });

    array<priority_queue<int, vector<int>, greater<int>>, 2> vals;
    array<int, 2> pref_val{0, 0};
    for (seg s : S) {
        for (int z = 0; z < 2; z++) {
            while (!vals[z].empty() && vals[z].top() <= s.l) {
                pref_val[z]++; vals[z].pop();
            }
        }
        for (int z = 0; z < 2; z++) {
            while (pref_val[z] < pref_val[!z]) {
                pref_val[z]++;
                if (!vals[z].empty()) vals[z].pop();
            }
        }
        vals[s.t].push(s.r);
    }
    cout << max(int(vals[0].size()) + pref_val[0], int(vals[1].size()) + pref_val[1]) << '\n';

    return 0;
}

Um_nik

常规的 dp 写法。用线段树维护每种颜色，每个右端点的 dp 值。这个程序的 dp 部分写得比较简便。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 1 << 19;
struct Node {
    int l, r;
    int val;
    int addAll;

    Node() : l(-1), r(-1), val(0), addAll(0) {}
    Node(int _l, int _r) : l(_l), r(_r), val(0), addAll(0) {}

    void add(int x) {
        val += x;
        addAll += x;
    }
};
Node tree[2][2 * N + 5];

void build() {
    for (int k = 0; k < 2; k++) {
        for (int i = 0; i < N; i++)
            tree[k][N + i] = Node(i, i + 1);
        for (int i = N - 1; i > 0; i--)
            tree[k][i] = Node(tree[k][2 * i].l, tree[k][2 * i + 1].r);
    }
}
void push(int k, int v) {
    for (int u = 2 * v; u < 2 * v + 2; u++) {
        tree[k][u].add(tree[k][v].addAll);
    }
    tree[k][v].addAll = 0;
}
void update(int k, int v) {
    tree[k][v].val = max(tree[k][2 * v].val, tree[k][2 * v + 1].val);
}

void setPoint(int k, int v, int p, int x) {
    if (p < tree[k][v].l || tree[k][v].r <= p) return;
    if (v >= N) {
        tree[k][v].val = max(tree[k][v].val, x);
        return;
    }
    push(k, v);
    for (int u = 2 * v; u < 2 * v + 2; u++)
        setPoint(k, u, p, x);
    update(k, v);
}
void addSegm(int k, int v, int l, int r, int x) {
    if (l <= tree[k][v].l && tree[k][v].r <= r) {
        tree[k][v].add(x);
        return;
    }
    if (l >= tree[k][v].r || tree[k][v].l >= r) return;
    push(k, v);
    for (int u = 2 * v; u < 2 * v + 2; u++)
        addSegm(k, u, l, r, x);
    update(k, v);
}
int getMax(int k, int v, int l, int r) {
    if (l <= tree[k][v].l && tree[k][v].r <= r) return tree[k][v].val;
    if (l >= tree[k][v].r || tree[k][v].l >= r) return 0;
    push(k, v);
    return max(getMax(k, 2 * v, l, r), getMax(k, 2 * v + 1, l, r));
}

int n;
int seg[N][3];
int xs[N];
int xsSz;
vector<pii> a[N];

int main()
{
    startTime = clock();
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    build();
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &seg[i][0], &seg[i][1], &seg[i][2]);
        seg[i][2]--;
        xs[xsSz++] = seg[i][0];
        xs[xsSz++] = seg[i][1];
    }
    xs[xsSz++] = -1;
    sort(xs, xs + xsSz);
    xsSz = unique(xs, xs + xsSz) - xs;
    for (int i = 0; i < n; i++) {
        int l = lower_bound(xs, xs + xsSz, seg[i][0]) - xs;
        int r = lower_bound(xs, xs + xsSz, seg[i][1]) - xs;
        int t = seg[i][2];
        a[r].push_back(mp(l, t));
    }
    int ans = 0;
    for (int x = 0; x < xsSz; x++) {
        for (pii s : a[x]) {
            addSegm(s.second, 1, 0, s.first, 1);
        }
        for (int t = 0; t < 2; t++) {
            int val = getMax(t, 1, 0, x);
            ans = max(ans, val);
            setPoint(t ^ 1, 1, x, val);
        }
    }
    printf("%d\n", ans);

    return 0;
}

neal

也是线段树的写法。

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using T_tree = int;
const T_tree T_INF = numeric_limits<T_tree>::max() / 2;

struct segment_change {
    T_tree to_add;

    segment_change(T_tree _to_add = 0) : to_add(_to_add) {}
};

struct segment {
    T_tree max_prefix, sum;

    segment(T_tree _max_prefix = -T_INF, T_tree _sum = 0) : max_prefix(_max_prefix), sum(_sum) {}

    void apply(const segment_change &change) {
        max_prefix += change.to_add;
        sum += change.to_add;
    }

    void join(const segment &other) {
        max_prefix = max(max_prefix, sum + other.max_prefix);
        sum += other.sum;
    }

    void join(const segment &a, const segment &b) {
        *this = a;
        join(b);
    }
};

int right_half[32];

struct max_prefix_sum_tree {
    static const bool POWER_OF_TWO_MODE = true;

    int tree_n = 0;
    vector<segment> tree;

    max_prefix_sum_tree(int n = -1) {
        if (n >= 0)
            init(n);
    }

    void init(int n) {
        if (POWER_OF_TWO_MODE) {
            tree_n = 1;

            while (tree_n < n)
                tree_n *= 2;
        } else {
            tree_n = n;
        }

        tree.assign(2 * tree_n, segment());
    }

    // Builds our tree from an array in O(n).
    void build(const vector<segment> &initial) {
        int n = int(initial.size());
        init(n);
        assert(n <= tree_n);

        for (int i = 0; i < n; i++)
            tree[tree_n + i] = initial[i];

        for (int position = tree_n - 1; position > 0; position--)
            tree[position].join(tree[2 * position], tree[2 * position + 1]);
    }

    segment query(int a, int b) const {
        assert(0 <= a && a <= b && b <= tree_n);
        segment answer;
        int r_size = 0;

        for (a += tree_n, b += tree_n; a < b; a /= 2, b /= 2) {
            if (a & 1)
                answer.join(tree[a++]);

            if (b & 1)
                right_half[r_size++] = --b;
        }

        for (int i = r_size - 1; i >= 0; i--)
            answer.join(tree[right_half[i]]);

        return answer;
    }

    segment query_single(int index) const {
        assert(0 <= index && index < tree_n);
        return tree[tree_n + index];
    }

    void join_up(int position) {
        while (position > 1) {
            position /= 2;
            tree[position].join(tree[2 * position], tree[2 * position + 1]);
        }
    }

    void update(int index, const segment_change &change) {
        assert(0 <= index && index < tree_n);
        int position = tree_n + index;
        tree[position].apply(change);
        join_up(position);
    }

    void update(int index, const segment &seg) {
        assert(0 <= index && index < tree_n);
        int position = tree_n + index;
        tree[position] = seg;
        join_up(position);
    }
};

struct add_max_seg_tree {
    // Build a `max_prefix_sum_tree` on the consecutive differences of the array.
    max_prefix_sum_tree tree;

    add_max_seg_tree(int n = -1) {
        if (n >= 0)
            init(n);
    }

    void init(int n) {
        tree.init(n);
    }

    void build(const vector<T_tree> &initial) {
        vector<segment> segment_initial(initial.size());
        T_tree previous = 0;

        for (int i = 0; i < int(initial.size()); i++) {
            T_tree value = initial[i] - previous;
            previous = initial[i];
            segment_initial[i] = segment(value, value);
        }

        tree.build(segment_initial);
    }

    T_tree query(int a, int b) const {
        return tree.query(0, a).sum + tree.query(a, b).max_prefix;
    }

    T_tree query_full() const {
        return tree.tree[1].max_prefix;
    }

    void update(int a, int b, segment_change change) {
        if (a < tree.tree_n)
            tree.update(a, change);

        if (b < tree.tree_n) {
            change.to_add *= -1;
            tree.update(b, change);
        }
    }

    void set_value(int index, T_tree value) {
        T_tree current = query(index, index + 1);
        update(index, index + 1, segment_change(value - current));
    }

    void maximize(int index, T_tree value) {
        T_tree current = query(index, index + 1);

        if (value > current)
            update(index, index + 1, segment_change(value - current));
    }
};

struct interval {
    int L, R, color;

    bool operator<(const interval &other) const {
        return L < other.L;
    }
};

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int N;
    cin >> N;
    vector<interval> intervals(N);
    vector<int> sorted;

    for (auto &inter : intervals) {
        cin >> inter.L >> inter.R >> inter.color;
        inter.color--;
        sorted.push_back(inter.L);
    }

    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int S = int(sorted.size());
    sort(intervals.begin(), intervals.end());

    for (auto &inter : intervals) {
        inter.L = int(lower_bound(sorted.begin(), sorted.end(), inter.L) - sorted.begin());
        inter.R = int(upper_bound(sorted.begin(), sorted.end(), inter.R) - sorted.begin()) - 1;
    }

    for (auto &inter : intervals)
        dbg(inter.L, inter.R, inter.color);

    add_max_seg_tree tree[2] = {add_max_seg_tree(S), add_max_seg_tree(S)};
    tree[0].build(vector<T_tree>(S, 0));
    tree[1].build(vector<T_tree>(S, 0));

    for (auto &inter : intervals) {
        tree[inter.color].update(inter.R + 1, S, +1);
        int value = 0;

        if (inter.L > 0)
            value = max(value, tree[!inter.color].query(0, inter.L));

        value = max(value, tree[inter.color].query(0, inter.R + 1));
        tree[inter.color].maximize(inter.R, value + 1);
    }

    cout << max(tree[0].query_full(), tree[1].query_full()) << '\n';
}

icecuber

这份代码的线段树写得比较简洁。

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

const int nax = 1<<19;
struct segTree {
  vector<ll> off, ma;
  segTree() {
    off.resize(nax*2);
    ma.resize(nax*2);
  }
  void add(int r, ll v) {
    for (int i = r+nax; i > 1; i >>= 1) {
      if (i&1) {
    off[i-1] += v;
      }
      ma[i>>1] = max(ma[i]+off[i], ma[i^1]+off[i^1]);
    }
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<tuple<int,int,int>> inp(n);
  map<int,int> comp;
  for (auto&[l,r,t] : inp) {
    cin >> l >> r >> t;
    t--;
    l--;
    comp[l];
    comp[r];
  }
  int c = 0;
  for (auto&[p,i] : comp) i = c++;
  vector<vector<vector<int>>> seg(2, vector<vector<int>>(c));
  for (auto&[l,r,t] : inp) {
    seg[t][comp[r]].push_back(comp[l]);
  }
  vector<vector<int>> dp(2, vector<int>(c));
  vector<segTree> tree(2);

  int ans = 0;
  for (int i = 0; i < c; i++) {
    for (int t : {0,1}) {
      for (int j : seg[t][i]) {
    tree[t].add(j+1, 1);
    //for (int k = 0; k <= j; k++)
    //  dp[!t][k]++;
      }
    }
    for (int t : {0,1}) {
      int v = 0;
      //for (int j = i-1; j >= 0; j--) {
      //v = max(v, dp[!t][j]);
      //}
      v = tree[!t].ma[1];
      ans = max(ans, v);
      tree[t].add(i+1,v);
      tree[t].add(i,-v);

      //dp[t][i] = v;
    }
  }
  cout << ans << endl;
}

natsugiri

#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
const LL INF = 1LL<<60;
struct Seg {
    LL ma; // minimum / maximum range query;
    Seg() : ma(-INF) {}
    Seg(LL val) : ma(val) {}
    friend Seg operator+(Seg x, const Seg &y) {
    amax(x.ma, y.ma);
    return x;
    }
};
const Seg unit = Seg();

struct Lazy {
    LL add, at_least;
    Lazy() : add(0), at_least(-INF) {}
    Lazy(LL a) : add(a), at_least(-INF) {}
    // l <= (val + a) <= m
    Lazy(LL a, LL l) : add(a), at_least(l) {}

    friend Seg operator*(Seg x, const Lazy &y) {
    x.ma = max(y.at_least, x.ma + y.add);
    return x;
    }

    // seg + below + above --> seg + new_below;
    // above(below(seg));
    friend Lazy& operator*=(Lazy &below, const Lazy &above) {
    below.add = max(-INF, min(INF, below.add + above.add));
    below.at_least = max(below.at_least + above.add, above.at_least);
    return below;
    }

    friend Lazy operator*(Lazy first, const Lazy &second) {
    return first *= second;
    }
};
const Lazy lazy_unit = Lazy();

struct SegTree {
    int n, m;
    vector<Seg> d;
    vector<Lazy> lazy;

    SegTree(int n_=1) : n(n_), m(2<<__lg(max(1, n_))), d(m*2, unit), lazy(m*2, lazy_unit) { }

    template<class Iter> SegTree(Iter begin, Iter end) : n(end - begin), m(2<<__lg(max(1, n))), d(m*2, unit), lazy(m*2, lazy_unit) {
    REP (i, n) { d[i+m] = Seg(*begin); ++begin; }
    for (int i=m; --i; ) d[i] = d[i*2] + d[i*2+1];
    }

    inline void force(int k) {
    if (k < m) { // Lazy down
        lazy[k*2] *= lazy[k];
        lazy[k*2+1] *= lazy[k];
        d[k] = eval(k*2) + eval(k*2+1);
        lazy[k] = lazy_unit;
    }
    }

    inline Seg eval(int k) const {
    return d[k] * lazy[k];
    }

    void apply(int x, int y, const Lazy &v) { apply(x, y, v, 1, 0, m); }

    void apply(int x, int y, const Lazy &v, int k, int l, int r) {
    if (r<=x || y<=l) return;
    if (x<=l && r<=y) { lazy[k] *= v; return; }
    force(k);
    apply(x, y, v, k*2, l, (l+r)/2); apply(x, y, v, k*2+1, (l+r)/2, r);
    d[k] = eval(k*2) + eval(k*2+1);
    }

    Seg query(int x, int y) { return query(x, y, 1, 0, m); }

    Seg query(int x, int y, int k, int l, int r) {
    if (r<=x || y<=l) return unit;
    if (x<=l && r<=y) return eval(k);
    force(k);
    return query(x, y, k*2, l, (l+r)/2) + query(x, y, k*2+1, (l+r)/2, r);
    }
};

int N;

struct Data {
    int l, r, t;

    bool operator<(const Data &o) const {
    return l < o.l;
    }
} D[200011];

VI RS;

void MAIN() {
    scanf("%d", &N);
    RS.push_back(0);
    REP (i, N) {
    scanf("%d%d%d", &D[i].l, &D[i].r, &D[i].t);
    RS.push_back(D[i].r);
    }
    sort(D, D+N);

    sort(RS.begin(), RS.end());
    RS.erase(unique(RS.begin(), RS.end()), RS.end());

    SegTree R(RS.size()), B(RS.size());
    R.apply(0, 1, Lazy(0, 0));
    B.apply(0, 1, Lazy(0, 0));

    REP (i, N) {
    int left = lower_bound(RS.begin(), RS.end(), D[i].l) - RS.begin();
    int pos = lower_bound(RS.begin(), RS.end(), D[i].r) - RS.begin();

    if (D[i].t == 1) {
        Seg seg = B.query(0, left);
        // R.apply(pos, RS.size(), Lazy(1));
        R.apply(pos, RS.size(), Lazy(1, seg.ma + 1));
    } else {
        Seg seg = R.query(0, left);
        // B.apply(pos, RS.size(), Lazy(1));
        B.apply(pos, RS.size(), Lazy(1, seg.ma + 1));
    }
    }

    LL ans = max(R.query(0, RS.size()).ma, B.query(0, RS.size()).ma);
    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

比赛记录 【Educational Codeforces Round 92】

E. Calendar Ambiguity

My Code

Code

ecnerwala

Um_nik

neal

icecuber

natsugiri

F. Bicolored Segments

My Code

Code

ecnerwala

Um_nik

neal

icecuber

natsugiri

比赛记录【Educational Codeforces Round 92】