• https://www.zhihu.com/question/548696144
• https://blog.csdn.net/liuzhangfeiabc/article/details/126594264

D1T1

• https://www.luogu.com.cn/problem/P8496

会维护区间绝对众数的话，这个就是送分题了。。难点自然只剩下合并操作，可以选择的有平衡树启发式合并，函数式线段树 或 Treap，这里考虑用函数式线段树。
然后单个序列只有尾部插入和删除，所有就是栈的链表，然后每个链表再对应一个线段树。
（什么，vector 居然比 stack 要快？）

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9, NN = 20*N;
int n, q;

struct Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
    int c[2][NN]; PII mx[NN]; int tot;
    int pp, dd;

    int new_node() {
        ++tot;
        return tot;
    }

    void add(int& x, int l = 1, int r = n + q) {
        if (!x) x = new_node();
        if (l == r) {
            mx[x].se = l;
            mx[x].fi += dd;
        } else {
            if (pp < mr) add(lc); else add(rc);
            mx[x] = max(mx[lx], mx[rx]);
        }
    }

    int query(int x, int l = 1, int r = n + q) {
        if (l == r) return mx[x].fi;
        return pp < mr ? query(lc) : query(rc);
    }

    void Add(int& x, int p, int d) {
        pp = p; dd = d; add(x);
    }

    int Query(int x, int p) {
        pp = p;
        return query(x);
    }

    int Merge(int x, int y) {
        if (!x || !y) return x | y;
        if (mx[lx].se == mx[rx].se) {
            mx[x].fi += mx[y].fi;
        } else {
            lx = Merge(lx, ly);
            rx = Merge(rx, ry);
            mx[x] = max(mx[lx], mx[rx]);
        }
        return x;
    }
} T;

VI a[N]; int l[N],head[N],tail[N],sz[N],rt[N];

inline void Add(int x, int y) {
    a[tail[x]].PB(y);
    T.Add(rt[x], y, 1);
    ++sz[x];
}

inline void Del(int x) {
    int &t = tail[x]; while(a[t].empty()) t = l[t];
    T.Add(rt[x],a[t].back(),-1); a[t].pop_back();
    --sz[x];
}

inline PII vote(int x) {
    PII t = T.mx[rt[x]];
    return {t.se, max(2*t.fi-sz[x], sz[x]&1)};
}
inline PII operator +(PII x, PII y) {
    if(x.fi == y.fi) return {x.fi, x.se + y.se};
    if(x.se > y.se) return {x.fi, x.se - y.se};
    return {y.fi, y.se - x.se};
}
inline int Query() {
    static int x[N], m;
    LL n = 0, c = 0; PII t = {0, 0};
    RD(m); REP(i, m) {
        n += sz[RD(x[i])];
        t = t + vote(x[i]);
    }
    REP(i, m) c += T.Query(rt[x[i]], t.fi);
    return c * 2 > n ? t.fi : -1;
}

inline void Merge(int x,int y,int z) {
    head[z] = head[x]; tail[z] = tail[y]; l[head[y]] = tail[x];
    rt[z] = T.Merge(rt[x], rt[y]); sz[z] = sz[x] + sz[y];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, q); REP_1(i, n) {
        tail[i] = head[i] = i;
        Rush Add(i,RD());
    }

    DO(q) {
        int x,y,z,op; RD(op); if (op == 1) RD(x,y),Add(x,y);
        else if (op == 2) Del(RD());
        else if (op == 3) OT(Query());
        else RD(x,y,z),Merge(x,y,z);
    }
}

D1T2

#include <lastweapon/io>
using namespace lastweapon;


const int N = int(1e3) + 5;
int n, k, l[N], r[N];
namespace judge {
  bool check() {
    if(k) return 0;
    for(int i = 1; i <= n; i++) if(l[i] != r[i]) return 0;
    return 1;
  }
  bool f[N][3][3];
  void solve() {
    memset(f, 0, sizeof(f));
    f[1][0][0] = 1;
    for(int i = 1; i <= n; i++)
      for(int j = 0; j <= 2; j++)
        for(int k = 0; k <= 2; k++) {
          if(!f[i][j][k]) continue;
          for(int st = 0; st <= 2; st++) {
            int val = l[i] - j - k - st;
            if(val < 0 || val == 1) continue;
            for(int nj = k; nj <= min(2, j + k); nj++) f[i + 1][nj][st] = 1;
          }
        }
    cout << f[n + 1][0][0] << "\n";
  }
}
void solve() {
  RD(n, k);
  REP_1(i, n) RD(l[i], r[i]);
  judge::solve();
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    Rush solve();
}

Posted by xiaodao
Category: 日常