CSA #70 Solution

两道垃圾套路题没写出来。

我好菜啊

Squared Ends

看见平方拆平方,用分治实现一个 CHT 即可。

注意边界。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<ll, ll>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 1e4 + 5;
const int MAXK = 105;
const ll oo = 1e18;

inline pr operator + (const pr & a, const pr & b) { return make_pair(a.fi + b.fi, a.se + b.se); }
inline pr operator - (const pr & a, const pr & b) { return make_pair(a.fi - b.fi, a.se - b.se); }

inline ll crs(const pr & a, const pr & b) { return a.fi * b.se - a.se * b.fi; }

inline ll sqr(ll x) { return x * x; }

int N, K, a[MAXN];
ll f[MAXK][MAXN];

int ord[MAXN], tmp[MAXN], top = 0;

pr q[MAXN], c[MAXN];

inline bool cmp(int x, int y) { return -a[x] < -a[y]; }

inline ll calc(pr o, int x) {return -2 * x * o.fi + o.se;}

void Work(int le, int ri, int o){
    if (le == ri) return;
    int mi = (le + ri) >> 1, cl = le, cr = mi + 1;
    up (i, le, ri) ord[i] <= mi ? tmp[cl++] = ord[i] : tmp[cr++] = ord[i];
    up (i, le, ri) ord[i] = tmp[i];
    Work(le, mi, o);
    up (i, le, mi) c[i] = make_pair(a[ord[i] + 1], f[o - 1][ord[i]] + sqr(a[ord[i] + 1]));
    top = 0;
    up (i, le, mi) {
        while (top >= 2 && crs(q[top] - c[i], q[top - 1] - c[i]) >= 0) top--;
        q[++top] = c[i];
    }
    cl = top;
    up (i, mi + 1, ri) {
        while (cl - 1 >= 1 && calc(q[cl - 1], a[ord[i]]) < calc(q[cl], a[ord[i]])) cl--;
        cmin(f[o][ord[i]], calc(q[cl], a[ord[i]]) + sqr(a[ord[i]]));
    }
    Work(mi + 1, ri, o);
    up (i, mi + 1, ri) c[i] = make_pair(a[ord[i] + 1], f[o - 1][ord[i]] + sqr(a[ord[i] + 1]));
    cl = le; cr = mi + 1;
    up (i, le, ri) {
        if (cl == mi + 1) tmp[i] = ord[cr++];
        else if (cr == ri + 1) tmp[i] = ord[cl++];
        else tmp[i] = c[cl] < c[cr] ? ord[cl++] : ord[cr++];
    }
    up (i, le, ri) ord[i] = tmp[i];
}

int main(){
    scanf("%d%d", &N, &K);
    up (i, 1, N) scanf("%d", &a[i]);
    up (i, 1, N) f[1][i] = sqr(a[i] - a[1]);
    up (o, 2, K) {
        up (i, 1, N) {
            ord[i] = i; 
            f[o][i] = oo;
        }
        sort(ord + o - 1, ord + N + 1, cmp);
        Work(o - 1, N, o);
    }
    printf("%lld\n", f[K][N]);
    return 0;
}

And or Max

这题很棒的样子。

我们发现本质上是一个多维的 0 / 1 区间 max/min,容易想到用吉司机线段树维护。

然后我们发现多维的标记可以叠加,直接维护就行了。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 2e5 + 5;
const int oo = 0x3f3f3f3f;

const int all = bin(21) - 1;

int N, Q, a[MAXN];

struct tree {
    int sor, sad, mx, tor, tad;
    tree () {
        sor = tor = 0;
        sad = tad = bin(21) - 1;
    }
}t[MAXN << 2];

inline void rel(int k){
    t[k].sor = t[k << 1].sor; 
    t[k].sad = t[k << 1].sad;
    t[k].mx = t[k << 1].mx;
    t[k].sor |= t[k << 1 | 1].sor;
    t[k].sad &= t[k << 1 | 1].sad;
    cmax(t[k].mx, t[k << 1 | 1].mx);
}

inline void mark(int k, int tad, int tor){
    t[k].sor &= tad; t[k].tor &= tad; t[k].sad &= tad; t[k].tad &= tad;
    t[k].sor |= tor; t[k].tor |= tor; t[k].sad |= tor;
    t[k].mx &= tad; t[k].mx |= tor; 
}

void Pushdown(int k){
    mark(k << 1, t[k].tad, t[k].tor);
    mark(k << 1 | 1, t[k].tad, t[k].tor);
    t[k].tad = bin(21) - 1;
    t[k].tor = 0;
}

void Build(int le, int ri, int k){
    if (le == ri) {
        t[k].sor = t[k].sad = t[k].mx = a[le];
        return;
    }
    int mi = (le + ri) >> 1;
    Build(le, mi, k << 1);
    Build(mi + 1, ri, k << 1 | 1);
    rel(k);
}

void cg_and(int le, int ri, int k, int L, int R, int x){
    if (le != ri) Pushdown(k);
    int mi = (le + ri) >> 1;
    if (L <= le && ri <= R) {
        int r = all ^ x;
        if ((t[k].sor & r) == (t[k].sad & r)) mark(k, x, 0);
        else {
            cg_and(le, mi, k << 1, L, R, x);
            cg_and(mi + 1, ri, k << 1 | 1, L, R, x);
            rel(k);
        }
        return;
    }
    if (L <= mi)     cg_and(le, mi, k << 1, L, R, x);
    if (mi + 1 <= R)     cg_and(mi + 1, ri, k << 1 | 1, L, R, x);
    rel(k);
}

void cg_or(int le, int ri, int k, int L, int R, int x){
    if (le != ri) Pushdown(k);
    int mi = (le + ri) >> 1;
    if (L <= le && ri <= R) {
        if ((t[k].sor & x) == (t[k].sad & x)) mark(k, all, x);
        else {
            cg_or(le, mi, k << 1, L, R, x);
            cg_or(mi + 1, ri, k << 1 | 1, L, R, x);
            rel(k);
        }
        return;
    }
    if (L <= mi)     cg_or(le, mi, k << 1, L, R, x);
    if (mi + 1 <= R)    cg_or(mi + 1, ri, k << 1 | 1, L, R, x);
    rel(k);
}

int get(int le, int ri, int k, int L, int R){
    if (le != ri) Pushdown(k);
    if (L <= le && ri <= R)     return t[k].mx;
    int mi = (le + ri) >> 1, mx = 0;
    if (L <= mi)     cmax(mx, get(le, mi, k << 1, L, R));
    if (mi + 1 <= R)    cmax(mx, get(mi + 1, ri, k << 1 | 1, L, R));
    return mx;
}

int main(){
    scanf("%d%d", &N, &Q);
    up (i, 1, N) scanf("%d", &a[i]);
    Build(1, N, 1);
    while (Q--) {
        int o, le, ri, x;
        scanf("%d%d%d", &o, &le, &ri);
        if (o == 1 || o == 2) {
            scanf("%d", &x);
            o == 1 ? cg_and(1, N, 1, le, ri, x) : cg_or(1, N, 1, le, ri, x);
        }else printf("%d\n", get(1, N, 1, le, ri));
    }
    return 0;
}