MENU

Problem b

20181105A problem.pdf

我们观察答案最多为多少
如果每次对$1\sim n$加一,最后询问$[1,n]$的答案
那么最多是$nlogn$
如果我们每次答案加一的复杂度是$O(1)$或者$O(logn)$
那么这道题就可以做了
现在就是怎么使均摊这个复杂度
我们改一下题目,刚开始$a_i=b_i$,修改是区间减$1$,当$a_i$变成$0$时,$i$的贡献$+1$,$a_i$重新变成$b_i$
我们用线段树维护区间最小值,如果当区间最小值为$0$时,递归处理左儿子和右儿子,如果当前区间最小值不为$0$就return,如果当前区间最小值为$0$且区间长度为$1$,则该点贡献$+1$,区间最小值由$0$变成$b_i$
我们发现这样每次修改只对区间最小值$-1$&打标记,复杂度$O(logn)$,当递归下去时,每递归到底一次复杂度$O(logn)$且答案$+1$,询问只需要区间求和就行,$O(logn)$
那么总复杂度就是$O(mlogn+nlog^2n)$

Orz Ycrpro

#include<cstdio>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("b.in", "r", stdin), freopen("b.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), a[1500000], lim[1500000], mark[1500000], sum[1500000], opt, l, r;
template<class T>inline T min(T a, T b) { return a < b ? a : b; }
void build(int p, int l, int r) {
    if (l == r) { lim[p] = a[l]; return; }
    int mid = l + r >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r), lim[p] = min(lim[p << 1], lim[p << 1 | 1]);
}
void pushdown(int p) {
    if (!mark[p])return;
    mark[p << 1] += mark[p], mark[p << 1 | 1] += mark[p], lim[p << 1] -= mark[p], lim[p << 1 | 1] -= mark[p], mark[p] = 0;
}
void gao(int p, int l, int r) {
    if (lim[p] > 1) { mark[p] += 1, lim[p] -= 1; return; }
    if (l == r) { lim[p] = a[l], ++sum[p]; return; }
    int mid = l + r >> 1;
    pushdown(p), gao(p << 1, l, mid), gao(p << 1 | 1, mid + 1, r), lim[p] = min(lim[p << 1], lim[p << 1 | 1]), sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
void assign(int p, int l, int r, int L, int R) {
    if (L > r || R < l)return;
    if (L <= l && R >= r) { gao(p, l, r); return; }
    pushdown(p);
    int mid = l + r >> 1;
    assign(p << 1, l, mid, L, R), assign(p << 1 | 1, mid + 1, r, L, R), lim[p] = min(lim[p << 1], lim[p << 1 | 1]), sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
int query(int p, int l, int r, int L, int R) {
    if (L > r || R < l)return 0;
    if (L <= l && R >= r)return sum[p];
    pushdown(p);
    int mid = l + r >> 1;
    return query(p << 1, l, mid, L, R) + query(p << 1 | 1, mid + 1, r, L, R);
}
int main() {
    for (int i = 1; i <= n; ++i)a[i] = ip.rd<int>();
    build(1, 1, n);
    while (m--) {
        opt = ip.rd<int>(), l = ip.rd<int>(), r = ip.rd<int>();
        if (opt == 1)assign(1, 1, n, l, r);
        else ip.print(query(1, 1, n, l, r)), ip.putc('\n');
    }
}
Leave a Comment

captcha
请输入验证码