HydroOJ 每日将从主题库及精选域中选出一题配以题解在此分享给大家。

如果你也想为 Hydro 提供每日一题,可以联系 Macesuted

每日一题将以评论的方式在此贴下发布,无关用户请勿直接回复本帖,允许用户发布二级评论(即允许评论每日一题)。

31 条评论

  • @ 2022-5-4 15:30:47

    #031 2022.5.4

    COCI2008-2009#4 PERIODNI

    标签:背包,笛卡尔树。

    题目大意

    给一个异形的棋盘,底对齐宽为 nn ,高度 hih_i 互不相同,求放置 kk 个车互不攻击的方案数。这里攻击定义为两车处在同一行或同一列,而且中间有连续的格子。

    1n,k500,1hi1061 \leq n, k \leq 500, 1 \leq h_i \leq 10^6

    题解

    考虑一个较低的列,它将区间划分为左右两边,高于这个列高的位置在左右两边互不攻击。

    找到全局最低的列,递归地跑两边的背包(棋子数,方案数),然后合并左右区间的背包,剩下的部分是在一个与该最低列同高的,宽度为区间长度减去已经选的列的矩形上放置 kk 个车,这个东西可以很快地组合数(选 kkkk 列然后选择一种排列代表棋子的位置):

    (xk)(yk)k!\binom{x}{k} \binom{y}{k} k!

    将合并得到的背包和当前的决策再做一遍卷积,得到当前区间的背包。

    由于 kk 比较小,暴力卷就行了。

    找区间最小值的过程实际上就是一个小根笛卡尔树,所以 O(n)\mathcal{O}(n) 预先建立笛卡尔树然后在树上跑这个背包的过程即可。

    注意在递归过程中子区间当前结点的决策高度应该是当前列的高度减去上次划分的高度(笛卡尔树的父节点)。

    然后如果刚开始想到用最小值划分区间类似的东西,就可以建出笛卡尔树来辅助思考。

    code

    const int maxn = 510, maxc = 1e6 + 10, mod = 1e9 + 7;
    inline int inc(int x, int y) { return (x += y) < mod ? x : x - mod; }
    inline int dec(int x, int y) { return (x -= y) < 0 ? x + mod : x; }
    inline int mul(int x, int y) { return 1ll * x * y % mod; }
    inline int qp(int x, int y) {
        int ret = 1 % mod;
        for(; y; y >>= 1) {
            if(y & 1) ret = mul(ret, x);
            x = mul(x, x);
        }
        return ret;
    }
    int a[maxn], ls[maxn], rs[maxn], siz[maxn], root;
    int f[maxn][maxn], tmp[maxn];
    int fac[maxc], invF[maxc];
    int n, k;
    
    inline int C(int x, int y) {
        return mul(fac[x], mul(invF[x - y], invF[y]));
    }
    inline int calc(int x, int y, int k) {
        if(min(x, y) < k) return 0;
        return mul(mul(C(x, k), C(y, k)), fac[k]);
    }
    void dfs(int cur, int pre) {
        siz[cur] = 1;
        if(ls[cur]) dfs(ls[cur], cur), siz[cur] += siz[ls[cur]];
        if(rs[cur]) dfs(rs[cur], cur), siz[cur] += siz[rs[cur]];
        memset(tmp,0,sizeof(tmp));
        rep(i,0,min(siz[ls[cur]],k))
            rep(j,0,min(k - i,siz[rs[cur]]))
                tmp[i + j] = inc(tmp[i + j], mul(f[ls[cur]][i], f[rs[cur]][j]));
        rep(i,0,min(siz[cur],k))
            rep(j,0,min(siz[cur] - 1, i))
              f[cur][i] = inc(f[cur][i], mul(tmp[j], calc(siz[cur] - j, a[cur] - a[pre], i - j)));
    }
    
    signed main() {
        n = read(); k = read();
        int c = n;
        rep(i,1,n) a[i] = read(), c = max(c, a[i]);
        if(n < k) {
            puts("0");
            return 0;
        }
        // factor & inv_factor
        fac[0] = 1;
        rep(i,1,c) fac[i] = mul(fac[i - 1], i);
        invF[c] = qp(fac[c], mod - 2);
        per(i,c - 1,0) invF[i] = mul(invF[i + 1], i + 1);
        // build cartesian tree
        stack<int> stk;
        rep(x,1,n) {
            int lst = 0;
            while(!stk.empty() && a[stk.top()] > a[x]) lst = stk.top(), stk.pop();
            if(stk.empty()) root = x;
            else rs[stk.top()] = x;
            ls[x] = lst;
            stk.push(x);
        }
        f[0][0] = 1;
        dfs(root, 0);
        printf("%d\n", f[root][k]);
        return 0;
    }
    
    👍 9
    👀 2
  • @ 2022-4-5 7:04:10

    #030 2022.4.5

    标签:最短路。

    Statement

    给出一个 nn 个点 mm 条边的无向图,每条边在 lil_i 时刻出现,rir_i 时刻消失。00 时刻时你在 11 号点上,每一时刻你都需要经过一条边移动到距离为 11 的另一个点上,不能停留在一个点上不动。每个点和每条边均可经过多次。问最早到达 nn 号点的时间,或判断无法到达 nn 号点。

    n,m5×105, 0l<r109n,m \le 5 \times 10^5,~0 \le l < r \le 10^9

    Solution

    Solution

    我们发现若我们在 tt 时刻从 xx 走到 yy,我们可以在这一条边上反复横跳让我们在 t+2, t+4, t + 2,~t + 4,~\dots 时刻均能到达 yy,直到该边消失。由于这些能到达 yy 的时刻奇偶性均相同,因此考虑将每个点拆分为两个,一个为奇点一个为偶点,每次到达奇点时的时刻为奇数,到达偶点的时刻为偶数。对于一条 xxyy 的边,拆点后即为 xx 的奇点向 yy 的偶点连边和 xx 的偶点向 yy 的奇点连边。

    考虑在拆完点后得到的图上跑最短路,但是将最短路状态记在点上是不妥的,因为点是不会消失的,因此无法判断长于最短路的某一个路径长度是否合法。考虑将最短路状态记在边上,对每条有向边记录其最早的到达这条边起点的时间。到达一个点的最早时间即为他的所有入边的最短路的最小值加一。

    Code

    View On GitHub

    /**
     * @file 827F.cpp
     * @author Macesuted (i@macesuted.moe)
     * @date 2022-04-03
     *
     * @copyright Copyright (c) 2022
     * @brief
     *      My Tutorial: https://macesuted.moe/article/cf827f
     *
     */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    namespace IO {
    const int SIZE = 1 << 20;
    char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1;
    int cache1[100], cache2[100];
    char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
    char iseoln(char c) { return c == '\n' || c == '\r'; }
    void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
    void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
    char buftop(void) { return Ir == Il && (fill(), 1), *Il; }
    char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
    void putch(char x) { return *Ol++ = x, Ol == Or && (flush(), 1), void(); }
    template <typename T = int>
    T read(void) {
        T x = 0, f = +1;
        char c = getch();
        while (c < '0' || c > '9') (c == '-') && (f = -f), c = getch();
        while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
        return x * f;
    }
    template <typename T>
    void write(T x) {
        if (!x) return putch('0');
        if (x < 0) putch('-'), x = -x;
        int top = 0;
        while (x) cache1[top++] = x % 10, x /= 10;
        while (top) putch(cache1[--top] ^ 48);
        return;
    }
    template <typename T>
    void writeDouble(T x, int dep = 10) {
        if (x < 0) putch('-'), x = -x;
        int64_t fx = x;
        x -= fx;
        for (int i = 0; i < dep; i++) cache2[i] = (x *= 10), x -= int(x);
        if (int(x * 10) > 4) {
            cache2[dep - 1]++;
            for (int i = dep - 1; i; i--)
                if (cache2[i] == 10) cache2[i] = 0, cache2[i - 1]++;
            if (cache2[0] == 10) cache2[0] = 0, fx++;
        }
        write(fx), putch('.');
        for (int i = 0; i < dep; i++) putch(cache2[i] ^ 48);
        return;
    }
    string getstr(const string& suf = "") {
        string s = suf;
        while (isspace(buftop())) getch();
        for (char* p = Il; Il != Ir; fill(), p = Il) {
            while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
            s.append(p, Il);
            if (Il < Ir) break;
        }
        return s;
    }
    string getline(const string& suf = "") {
        string s = suf;
        while (iseoln(buftop())) getch();
        for (char* p = Il; Il != Ir; fill(), p = Il) {
            while (Il < Ir && !iseoln(*Il) && *Il != EOF) Il++;
            s.append(p, Il);
            if (Il < Ir) break;
        }
        return s;
    }
    void putstr(string str, int begin = 0, int end = -1) {
        if (end == -1) end = str.size();
        for (int i = begin; i < end; i++) putch(str[i]);
        return;
    }
    struct Flusher_ {
        ~Flusher_() { flush(); }
    } io_flusher_;
    }  // namespace IO
    using IO::getch;
    using IO::getline;
    using IO::getstr;
    using IO::putch;
    using IO::putstr;
    using IO::read;
    using IO::write;
    using IO::writeDouble;
    
    bool mem1;
    
    #define maxn 500005
    
    typedef tuple<int, int, int> tiii;
    
    vector<vector<tiii>> graph;
    vector<vector<tiii>::iterator> cur;
    int dist[maxn];
    
    void addEdge(int x, int y, int l, int r) {
        return l <= r &&
                   (graph[x].emplace_back(l + (l & 1), r - (r & 1), y), graph[y].emplace_back(l + !(l & 1), r - !(r & 1), x), 1),
               void();
    }
    
    void solve(void) {
        int n = read(), m = read();
        graph.resize(2 * n + 1), cur.resize(2 * n + 1);
        for (int i = 1; i <= m; i++) {
            int x = read(), y = read(), l = read(), r = read() - 1;
            addEdge(x, y + n, l, r), addEdge(y, x + n, l, r);
        }
        for (int i = 1; i <= 2 * n; i++) sort(cur[i] = graph[i].begin(), graph[i].end());
        memset(dist, 0x3f, sizeof(dist)), dist[1] = 0;
        static priority_queue<tiii, vector<tiii>, greater<tiii>> que;
        while (!que.empty()) que.pop();
        while (cur[1] != graph[1].end() && get<0>(*cur[1]) == 0) que.emplace(1, get<1>(*cur[1]) + 1, get<2>(*cur[1])), cur[1]++;
        while (!que.empty()) {
            auto [l, r, x] = que.top();
            que.pop(), dist[(x - 1) % n + 1] = min(dist[(x - 1) % n + 1], l);
            for (auto& i = cur[x]; i != graph[x].end() && get<0>(*i) <= r; i++)
                if (get<1>(*i) >= l) que.emplace(max(l, get<0>(*i)) + 1, get<1>(*i) + 1, get<2>(*i));
        }
        return write(dist[n] == 0x3f3f3f3f ? -1 : dist[n]), putch('\n');
    }
    
    bool mem2;
    
    int main() {
        ios::sync_with_stdio(false);
    #ifdef MACESUTED
        cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
    #endif
    
        int _ = 1;
        while (_--) solve();
    
    #ifdef MACESUTED
        cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
    #endif
        return 0;
    }
    
    👍 8
    ❤️ 6
  • @ 2022-3-30 9:07:40

    #029 2022.3.30

    Jelly-Oxygen Beans

    标签:数论。

    题目大意

    给一个正整数 NN ,求 1MN[(NmodM)M]\sum_{1 \leq M \leq N}[(N \bmod M) \mid M]

    N1012N \leq 10^{12}

    题解

    N=kM+rN = kM + r , 对于满足题意的 MMM=rsM = rs ,其中 s1s \neq 1

    此时 N=(ks+1)rN = (ks + 1)r

    r1r \neq 1 ,枚举 rr ,求 Nr1\frac{N}{r} - 1 的非 11 约数个数和即可。

    r=0r = 0 实际上就是约数。

    这种枚举是不漏的,因为我们对于每个 rr 求出了所有可能的 MM

    这种枚举是不重的,首先每个 MM 对应唯一的 rr ,而对于每个 rr ,不同的 ss 又能得到不同的 MM

    这种枚举的复杂度的表达式大概是

    O(dnd)\mathcal{O}(\sum_{d \mid n} \sqrt d)

    看起来是 O\mathcal{O} (能过) ,我在 vp 的时候对着那张约数个数级别表格看了好久一度以为很难过,实际上是不高于 O(NlogN)\mathcal{O}(\sqrt {N} \log N ) 。而且随机数据下跑的非常快。

    code

    int test(ll x) {
        if(x == 0) return 0;
        int ret = 0;
        for(ll i = 1; i * i <= x; ++ i) {
            if(x % i == 0)
                ret += 2;
            if(x == i * i) -- ret;
        }
        return ret - 1;
    }
    
    int main() {
        ll n, ans = 0;
        scanf("%lld", &n);
        for(ll i = 1; i * i <= n; ++ i) {
            if(n % i != 0) continue;
            ll t = n / i;
            ans += test(i - 1) + 1;
            if(n == i * i) continue;
            ans += test(t - 1) + 1;
        }
        printf("%lld\n", ans);
        return 0;
    }
    

    关于复杂度

    约数和函数:

    σk(n):=dndk\sigma_k(n) := \sum_{d \mid n} d^k

    这个东西在 k<1k < 1 的时候的阶的估计大概是这样的:

    σk(n)nkexp{(1+o(1))(logn)1k(1k)loglogn}\sigma_k(n) \leq n ^ k \exp \{ (1 + o(1)) \frac{(\log n)^{1 - k}}{(1 - k)\log \log n} \}

    感觉这个东西没有初阶的证明方法。

    姑且认为 dndO(nlogn)\sum_{d \mid n} \sqrt d \sim \mathcal{O}(\sqrt n \log n)

    👍 7
    ❤️ 5
    • @ 2022-3-29 7:27:40

      #028 2022.3.29

      标签:构造。

      Statement

      这是一道交互题。

      已知 nn,有一个未知数 xx1xn1 \le x \le n ),你需要求出 xx 的值。

      有一个集合 S={1,2,,n}S = \{1,2,\dots ,n\} 。你可以进行不超过 10410^4 次操作。每次操作可以是如下三种之一:

      A:A a\texttt{A:A a},表示求出 SSaa 的倍数的个数 (1an1\le a\le n

      B:B a\texttt{B:B a},表示求出 SSaa 的倍数的个数并将这些数从 SS 中删去(xx 是不会被删掉的) (2an2\le a \le n

      C:C a\texttt{C:C a},表示你知道了 x=ax = a1 lean1\ le a \le n

      所有的 aa 均为整数

      Solution

      Solution

      交互题考虑分析操作和规模,对于 B\texttt{B} 操作,我们发现如果 aa 的倍数中有 xx,那么最后删除的时候是不会删除 xx 的,但是我们又可以使用 A\texttt{A} 操作来得到集合中 aa 的倍数。

      如果 xx 不是 aa 的倍数,那么使用 B\texttt{B} 操作之后再使用一次 A\texttt{A} 操作得到的回复应该是 00,否则为 11

      因此,我们有了一种暴力的思路,我们考虑对于 10510^5 内所有质数,都执行一遍上面的操作,然后我们可以确定出 xx 是由哪些质因子构成的,然后最后我们再询问这些质因子的次幂即可。

      那么,这么做的操作次数为多少呢?

      10510^5 范围内的质数有 95929592 个,我们至少对每个质数都执行了两遍操作,然后还有最后找出数 xx 又需要一些次数,超出规定的 10410^4 操作次数。

      考虑优化我们的交互策略,对质数进行根号分治。

      将大于 316316 的质数和小于 316316 的质数分别进行处理。

      对于大于 316316 的质数,任何 xx 都最多只会有一个 11 这么的质因数出现,否则就超出了值域 10510^5

      对于小于 316316 的质数,只有 6565 个质数。

      对于这些质数,我们先进行之前的策略,得到 xx 的小质数因子,并且询问出他应有的次幂。

      可以计算出,这部分操作次数最多为 238238 次。

      然后执行完之后只会有 1,x1,xxx 的大质数因子。

      然后对于大质数,还拥有 95279527 个。

      假设之前得到的小质数因子乘积 dd 大于 11

      那么这个数是个合数,直接询问所有大质数 p×dp\times d 是否存在,如果存在那么 x=p×dx = p \times d

      这部分的操作次数最多为 238+9527+1=9766238+9527+1=9766

      如果 d=1d=1 的话,那么证明我们的数 xx 是个质数或者为 11,他就在后面的大质数因子中。

      那么不能照搬上面的做法了,而直接暴力操作次数要乘二,就超了。

      人类智慧,接下来的序列中只有 11 和大质数。

      对大质数进行分块,每 100100 个大质数分一块,每次连续删 100100 个大质数。

      然后询问 A 1\texttt{A 1} 可以得到现在序列中数量,按理来说应该是每次减少 100100 个,如果有一次减少的是 9999 个,证明 xx 在这一块中,然后暴力递归找即可。

      这部分的操作次数最终也不会超过 10410^4

      实际上我调了一下块长为 8686,因为我写丑了。

      Code

      // 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
      // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱!
      #include <bits/stdc++.h>
      #define int long long
      using namespace std;
      #define FOR(i, l, r) for(int i = (l); i <= r; ++i)
      #define REP(i, l, r) for(int i = (l); i <  r; ++i)
      #define DFR(i, l, r) for(int i = (l); i >= r; --i)
      #define DRP(i, l, r) for(int i = (l); i >  r; --i)
      #define FORV(i, ver) for(int i = 0; i < ver.size(); i++)
      #define FORP(i, ver) for(auto i : ver)
      template<class T>T wmin(const T &a, const T &b) {return a < b ? a : b;}
      template<class T>T wmax(const T &a, const T &b) {return a > b ? a : b;}
      template<class T>bool chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
      template<class T>bool chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
      inline int read() {
        int x = 0, f = 1;  char ch = getchar();
        while( !isdigit(ch) ) { if(ch == '-') f = -1;  ch = getchar();  }
        while( isdigit(ch) ) {  x = (x << 1) + (x << 3) + (ch ^ 48);  ch = getchar();  }
        return x * f;
      }
      const int N = 2e6;
      int n, vis[N], pr[N], tot, c[N], num;
      void prime(int n) {
        FOR (i, 2, n) {
          if (vis[i]) continue;
          pr[++tot] = i;
          for (int j = i; j <= n; j += i) vis[j] = 1;
        }
      }
      int A(int x) {
        cout << "A " << x << "\n";  cout.flush();
        int qwq;  cin >> qwq;  return qwq;
      }
      void B(int x) {
        cout << "B " << x << "\n";  cout.flush();
        int qwq;  cin >> qwq;
      }
      void C(int x) {
        cout << "C " << x << "\n";  cout.flush();  exit(0);
      }
      signed main () {
        ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
        n = read(); prime(n);
        if (n == 1) { C(1); }
        int now = 1;
        FOR (i, 1, tot) {
          if (pr[i] > 316) break;
          int x = pr[i];
          B(x);
          if ( A(x) == 1 ) {
            now = now * x;
            int gtr = x;
            while (1) {
              gtr *= x;
              if (gtr > n) break;
              if ( A(gtr) == 1 ) now *= x;
              else break;
            }
          }
        }
        if (now == 1) {
          int ans = 1;
          FOR (i, 1, tot) {
            if (pr[i] < 316) continue;
            c[++num] = pr[i];
          }
          int siz = 86, bel = (num - 1) / siz + 1;
          int cnt = A(1);
          FOR (i, 1, bel) {
            int l = (i - 1) * siz + 1;
            int r = wmin(num, i * siz);
            int len = r - l + 1;
            FOR (j, l, r) {
              int x = c[j];
              B(x);
            }
            int qaq = A(1);
            if (qaq == cnt - len) { cnt -= len;  continue;  }
            FOR (j, l, r) {
              int x = c[j];
              int qwq = A(x);
              if (qwq) C(x);
            }
          }
          C(1);
        }
        FOR (i, 1, tot) {
          if (pr[i] < 316) continue;
          int x = pr[i];
          if (x * now > n) break;
          if (A(x * now) == 1) C(x * now);
        }
        C(now);
        return 0;
      }
      
      ❤️ 8
      👍 4
      👎 3
      👀 3
      🤣 3
      😕 2
      🌿 2
      🤔 2
      🕊️ 2
      🍋 2
      😄 2
      • @ 2022-3-27 7:49:49

        #027 2022.3.27

        标签:数据结构,平衡树,模拟。

        Statement

        维护一个长为 nn 的 0/1 序列 aa,有 mm 个操作:

        • 1 l r:把区间 [l, r][l,~r] 的数变成 00
        • 2 l r:把区间 [l, r][l,~r] 的数变成 11
        • 3 l r[l, r1][l,~r-1] 内所有数 aia_i,变为 aia_iai+1a_{i+1} 按位或的值,这些数同时进行这个操作。
        • 4 l r[l+1, r][l+1,~r] 内所有数 aia_i,变为 aia_iai1a_{i-1} 按位或的值,这些数同时进行这个操作。
        • 5 l r[l, r1][l,~r-1] 内所有数 aia_i,变为 aia_iai+1a_{i+1} 按位与的值,这些数同时进行这个操作。
        • 6 l r[l+1, r][l+1,~r] 内所有数 aia_i,变为 aia_iai1a_{i-1} 按位与的值,这些数同时进行这个操作。
        • 7 l r:查询区间 [l, r][l,~r] 内的元素和。

        强制在线。

        n, m3×106n,~m \le 3 \times 10^6

        Solution

        Solution

        我们显然无法使用平衡树直接维护每个点的单点信息,因为题目中给出的操作对于区间中的每一个元素均与它两边的元素进行了运算,难以直接维护每个单点的信息。

        所以我们考虑将原序列拆分为一些区间,使之可以较方便地处理题目中给出的这些操作。

        一个比较显然的想法是将原序列拆分为若干段同色的极长段。比如将 0, 1, 1, 0, 0, 10,~1,~1,~0,~0,~1 划分为 [0] [1, 1] [0, 0] [1][0]~[1,~1]~[0,~0]~[1]。容易发现这样划分之后,如果一个操作覆盖了某一个区间,我们可以方便地计算出该操作对该区间的影响:

        • 1 操作: 所覆盖的 1 区间均变为 0 区间。
        • 2 操作: 所覆盖的 0 区间均变为 1 区间。
        • 3 操作: 所覆盖的 0 区间右端点 1-1,所覆盖的 1 区间左端点 1-1
        • 4 操作: 所覆盖的 0 区间左端点 +1+1,所覆盖的 1 区间右端点 +1+1
        • 5 操作: 所覆盖的 0 区间左端点 1-1,所覆盖的 1 区间右端点 1-1
        • 6 操作: 所覆盖的 0 区间右端点 +1+1,所覆盖的 1 区间左端点 +1+1

        同时,由于我们需要在下放标记前计算出某个询问区间对应的元素和,所以我们需要保证每一个区间均为极长区间,也就是不能让空区间留在平衡树中。

        由于在整个过程中于平衡树上出现的区间数量是 O(n+m)O(n+m) 级别的,所以我们可以在每个平衡树结点上记录其子树内最短的 0/1 区间的长度,在该长度达到 0 时暴力地向下搜索找到空区间并删除,对于每个空区间我们需要花费 O(logn)O(\log n) 的时间复杂度,因此总共花费在删除空区间操作上的时间是 O((n+m)logn)O((n+m)\log n) 级别的,可以接受。

        根据上面提到的方法维护平衡树即可。

        Code

        编写代码用时 3h,调试用时 2h,使用指针版 FhqTreap,由于卡常使用了内存池并省去了回收内存操作。

        下面是一些注意事项和建议:

        • 写代码时务必多画图,仔细考虑每一个操作的边界情况。(即操作区间的左右端点所在区间是否需要被修改的情况)
        • 由于代码较长建议每写完几个操作就进行简单的测试以检验其正确性。
        • 如果 WA 并且找不到显然的错误,可以在每次操作结束后输出整棵平衡上的所有区间的信息,配合手动模拟或是暴力代码测试几组数据。

        View on GitHub

        /**
         * @author Macesuted (i@macesuted.moe)
         * @copyright Copyright (c) 2021
         * @brief
         *      My solution: https://www.macesuted.cn/article/lg5066/
         */
        
        #include <bits/stdc++.h>
        using namespace std;
        
        namespace io {
        #define SIZE (1 << 20)
        char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
        int f, qr;
        inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
        inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
        inline void putch(char x) {
            *oS++ = x;
            if (oS == oT) flush();
            return;
        }
        string getstr(void) {
            string s = "";
            char c = getch();
            while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
            while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
            return s;
        }
        void putstr(string str, int begin = 0, int end = -1) {
            if (end == -1) end = str.size();
            for (register int i = begin; i < end; i++) putch(str[i]);
            return;
        }
        template <typename T>
        inline T read() {
            register T x = 0;
            for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                if (c == '-') f = -1;
            for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
            return x * f;
        }
        template <typename T>
        inline void write(const T& t) {
            register T x = t;
            if (!x) putch('0');
            if (x < 0) putch('-'), x = -x;
            while (x) qu[++qr] = x % 10 + '0', x /= 10;
            while (qr) putch(qu[qr--]);
            return;
        }
        struct Flusher_ {
            ~Flusher_() { flush(); }
        } io_flusher_;
        }  // namespace io
        using io::getch;
        using io::getstr;
        using io::putch;
        using io::putstr;
        using io::read;
        using io::write;
        
        #define maxn 3000005
        #define INF 0x3f3f3f3f
        
        class FhqTreap {
           private:
            struct Node {
                int rank;
                int col;             // 区间颜色
                int sum;             // 子树和
                int siz[2];          // 子树内 0/1 区间数量
                int tl, tr;          // 区间左右端点
                int deltaL, deltaR;  // 1 区间左右端点偏移量
                int minLen[2];       // 子树内最短 0/1 区间长度
                Node *l, *r;         // 平衡树左右孩子
                Node(void) {}
                Node(int _rank, int _col, int _tl, int _tr) {
                    rank = _rank;
                    col = _col;
                    tl = _tl, tr = _tr;
                    l = r = NULL;
                    reset();
                }
                // 重新计算该点的单点信息
                void reset(void) {
                    siz[col] = 1, siz[!col] = 0;
                    sum = col * (tr - tl + 1);
                    deltaL = deltaR = 0;
                    minLen[col] = tr - tl + 1, minLen[!col] = INF;
                    return;
                }
                Node operator+(const Node& b) const {
                    Node a = *this;
                    a.sum += b.sum;
                    a.siz[0] += b.siz[0], a.siz[1] += b.siz[1];
                    a.minLen[0] = min(a.minLen[0], b.minLen[0]), a.minLen[1] = min(a.minLen[1], b.minLen[1]);
                    return a;
                }
            };
        
            Node pool[10000000];
            int tail = 0;
        
            Node* root;
            queue<Node*> needErase;  // 需要被删除的结点
        
            static const long long kMul = 0x9ddfea08eb382d69ULL;
            long long Seed = 1145141919810;
            inline long long fingerPrint(long long x) {
                return x *= kMul, x ^= x >> 47, x *= kMul, x ^= x >> 47, x *= kMul, x ^= x >> 47, x * kMul;
            }
            inline int frand(void) { return Seed += fingerPrint(Seed); }
        
            inline Node* newNode(int val, int l, int r) { return &(pool[tail++] = Node(frand(), val, l, r)); }
        
            inline void update(Node* p, int dl, int dr) {
                if (p == NULL) return;
                p->deltaL += dl, p->deltaR += dr;
                p->minLen[0] -= dl + dr, p->minLen[1] += dl + dr;
                p->sum += (dl + dr) * p->siz[1];
                if (p->col == 1)
                    p->tl -= dl, p->tr += dr;
                else
                    p->tl += dr, p->tr -= dl;
                return;
            }
            void findEmpty(Node* p) {
                if (p == NULL) return;
                if (p->minLen[0] && p->minLen[1]) return;
                pushDown(p);
                if (p->tl > p->tr) needErase.push(p);
                findEmpty(p->l), findEmpty(p->r);
                return;
            }
            void eraseEmpty(void) {
                while (!needErase.empty()) {
                    Node* p = needErase.front();
                    needErase.pop();
                    Node *nodeL = NULL, *treeM = NULL, *nodeR = NULL, *treeR = NULL;
                    split1(root, root, treeR, p->tl - 1), split1(treeR, treeM, treeR, p->tl);
                    split2(root, root, nodeL, p->tl - 2);
                    if (p == treeM)
                        nodeR = (p->l == NULL) ? p->r : p->l;
                    else
                        nodeR = treeM, nodeR->l = nodeR->r = NULL;
                    // delete p;
                    if (nodeL != NULL && nodeR != NULL) nodeL->tr = nodeR->tr, nodeL->reset(), /* delete nodeR, */ nodeR = NULL;
                    merge(root, root, nodeL), merge(root, root, nodeR), merge(root, root, treeR);
                }
                return;
            }
            // void destroy(Node* p) {
            //     if (p == NULL) return;
            //     if (p->l != NULL) destroy(p->l);
            //     if (p->r != NULL) destroy(p->r);
            //     delete p;
            //     return;
            // }
            void pushDown(Node* p) {
                if (!p->deltaL && !p->deltaR) return;
                if (p->l != NULL) update(p->l, p->deltaL, p->deltaR);
                if (p->r != NULL) update(p->r, p->deltaL, p->deltaR);
                p->deltaL = p->deltaR = 0;
                return;
            }
            inline void pushUp(Node* p) {
                p->reset();
                if (p->l != NULL) *p = *p + *(p->l);
                if (p->r != NULL) *p = *p + *(p->r);
                return;
            }
        
            // 将对应区间左端点 <= p 的部分划分到 tree1,左端点 > p 的部分划分到 tree2
            void split1(Node* root, Node*& tree1, Node*& tree2, int p) {
                if (root == NULL) return tree1 = tree2 = NULL, void();
                pushDown(root);
                if (root->tl <= p)
                    tree1 = root, split1(root->r, tree1->r, tree2, p);
                else
                    tree2 = root, split1(root->l, tree1, tree2->l, p);
                return pushUp(root);
            }
            // 将对应区间右端点 <= p 的部分划分到 tree1,右端点 > p 的部分划分到 tree2
            void split2(Node* root, Node*& tree1, Node*& tree2, int p) {
                if (root == NULL) return tree1 = tree2 = NULL, void();
                pushDown(root);
                if (root->tr <= p)
                    tree1 = root, split2(root->r, tree1->r, tree2, p);
                else
                    tree2 = root, split2(root->l, tree1, tree2->l, p);
                return pushUp(root);
            }
            void merge(Node*& root, Node* tree1, Node* tree2) {
                if (tree1 == NULL) return root = tree2, void();
                if (tree2 == NULL) return root = tree1, void();
                if (tree1->rank < tree2->rank)
                    pushDown(root = tree1), merge(root->r, tree1->r, tree2);
                else
                    pushDown(root = tree2), merge(root->l, tree1, tree2->l);
                return pushUp(root);
            }
        
            void print(Node* root) {
                if (root == NULL) return;
                pushDown(root);
                if (root->l != NULL) print(root->l);
                cerr << '[' << root->tl << '~' << root->tr << ':' << root->col << ']';
                if (root->r != NULL) print(root->r);
                return;
            }
        
           public:
            FhqTreap(void) { root = NULL; }
            void pushBack(int l, int r, int val) {
                Node* p = newNode(val, l, r);
                merge(root, root, p);
                return;
            }
            void opt1_2(int l, int r, int val) {
                Node *nodeL = NULL, *p = NULL, *nodeR = NULL, *treeR = NULL;
                split2(root, root, p, l - 1), split1(p, p, treeR, r);
                split1(p, nodeL, p, l - 1), split2(p, p, nodeR, r);
                if (nodeL != NULL) {
                    if (nodeL->tr > r) nodeR = newNode(nodeL->col, r, nodeL->tr);
                    nodeL->tr = l - 1, nodeL->reset();
                } else
                    split2(root, root, nodeL, l - 2);
                if (nodeR != NULL)
                    nodeR->tl = r + 1, nodeR->reset();
                else
                    split1(treeR, nodeR, treeR, r + 1);
                // destroy(p);
                p = newNode(val, l, r);
                if (nodeL != NULL && p->col == nodeL->col) {
                    p->tl = nodeL->tl, p->reset();
                    // delete nodeL;
                    nodeL = NULL;
                }
                if (nodeR != NULL && p->col == nodeR->col) {
                    p->tr = nodeR->tr, p->reset();
                    // delete nodeR;
                    nodeR = NULL;
                }
                merge(root, root, nodeL), merge(root, root, p), merge(root, root, nodeR), merge(root, root, treeR);
                return;
            }
            void opt3(int l, int r) {
                r--;
                Node *treeM = NULL, *treeR = NULL, *node = NULL;
                split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r);
                split1(treeM, node, treeM, l);
                if (node != NULL && node->col == 1)
                    merge(root, root, node);
                else
                    merge(treeM, node, treeM);
                node = NULL;
                split2(treeM, treeM, node, r - 1);
                if (node != NULL && node->col == 0) {
                    if (node->tr > r)
                        merge(treeR, node, treeR);
                    else {
                        merge(treeM, treeM, node);
                        Node* nodeR = NULL;
                        split1(treeR, nodeR, treeR, r + 1);
                        merge(treeM, treeM, nodeR);
                    }
                } else
                    merge(treeM, treeM, node);
                if (treeM != NULL) update(treeM, 1, 0);
                merge(root, root, treeM), merge(root, root, treeR);
                findEmpty(root), eraseEmpty();
                return;
            }
            void opt4(int l, int r) {
                l++;
                Node *treeM = NULL, *treeR = NULL, *node = NULL;
                split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r);
                split1(treeM, node, treeM, l);
                if (node != NULL && node->col == 0) {
                    if (node->tl < l)
                        merge(root, root, node);
                    else {
                        merge(treeM, node, treeM);
                        Node* nodeL = NULL;
                        split2(root, root, nodeL, l - 2);
                        merge(treeM, nodeL, treeM);
                    }
                } else
                    merge(treeM, node, treeM);
                node = NULL;
                split2(treeM, treeM, node, r - 1);
                if (node != NULL && node->col == 1)
                    merge(treeR, node, treeR);
                else
                    merge(treeM, treeM, node);
                if (treeM != NULL) update(treeM, 0, 1);
                merge(root, root, treeM), merge(root, root, treeR);
                findEmpty(root), eraseEmpty();
                return;
            }
            void opt5(int l, int r) {
                r--;
                Node *treeM = NULL, *treeR = NULL, *node = NULL;
                split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r);
                split1(treeM, node, treeM, l);
                if (node != NULL && node->col == 0)
                    merge(root, root, node);
                else
                    merge(treeM, node, treeM);
                node = NULL;
                split2(treeM, treeM, node, r - 1);
                if (node != NULL && node->col == 1) {
                    if (node->tr > r)
                        merge(treeR, node, treeR);
                    else {
                        merge(treeM, treeM, node);
                        Node* nodeR = NULL;
                        split1(treeR, nodeR, treeR, r + 1);
                        merge(treeM, treeM, nodeR);
                    }
                } else
                    merge(treeM, treeM, node);
                if (treeM != NULL) update(treeM, 0, -1);
                merge(root, root, treeM), merge(root, root, treeR);
                findEmpty(root), eraseEmpty();
                return;
            }
            void opt6(int l, int r) {
                l++;
                Node *treeM = NULL, *treeR = NULL, *node = NULL;
                split2(root, root, treeM, l - 1), split1(treeM, treeM, treeR, r);
                split1(treeM, node, treeM, l);
                if (node != NULL && node->col == 1) {
                    if (node->tl < l)
                        merge(root, root, node);
                    else {
                        merge(treeM, node, treeM);
                        Node* nodeL = NULL;
                        split2(root, root, nodeL, l - 2);
                        merge(treeM, nodeL, treeM);
                    }
                } else
                    merge(treeM, node, treeM);
                node = NULL;
                split2(treeM, treeM, node, r - 1);
                if (node != NULL && node->col == 0)
                    merge(treeR, node, treeR);
                else
                    merge(treeM, treeM, node);
                if (treeM != NULL) update(treeM, -1, 0);
                merge(root, root, treeM), merge(root, root, treeR);
                findEmpty(root), eraseEmpty();
                return;
            }
            int opt7(int l, int r) {
                Node *node = NULL, *p = NULL, *treeR = NULL;
                split2(root, root, p, l - 1), split1(p, p, treeR, r);
                int answer = 0;
                if (p != NULL) answer += p->sum;
                split1(p, node, p, l - 1);
                if (node != NULL) answer -= node->col * (l - node->tl);
                merge(p, node, p);
                node = NULL;
                split2(p, p, node, r);
                if (node != NULL) answer -= node->col * (node->tr - r);
                merge(p, p, node);
                merge(root, root, p), merge(root, root, treeR);
                return answer;
            }
            inline void print(void) { return print(root), cerr << endl, void(); }
        };
        
        FhqTreap treap;
        
        int a[maxn];
        
        int main() {
            int n = read<int>(), m = read<int>();
            for (register int i = 1; i <= n; i++) a[i] = read<int>();
            int last = 1;
            for (register int i = 2; i <= n; i++)
                if (a[i] != a[i - 1]) treap.pushBack(last, i - 1, a[i - 1]), last = i;
            treap.pushBack(last, n, a[n]);
            last = 0;
            while (m--) {
                int opt = read<int>(), l = last ^ read<int>(), r = last ^ read<int>();
                if (opt == 1)
                    treap.opt1_2(l, r, 0);
                else if (opt == 2)
                    treap.opt1_2(l, r, 1);
                else if (opt == 3)
                    treap.opt3(l, r);
                else if (opt == 4)
                    treap.opt4(l, r);
                else if (opt == 5)
                    treap.opt5(l, r);
                else if (opt == 6)
                    treap.opt6(l, r);
                else
                    write(last = treap.opt7(l, r)), putch('\n');
            }
            return 0;
        }
        
        👍 6
        • @ 2022-3-26 7:08:42

          #026 2022.3.26

          标签:构造,贪心。

          Statement

          在数轴上给出 mm 个点和 nn 个询问,每个询问给出一个线段,初始放在 [li, ri][l_i,~r_i] 上,你需要移动该线段使得该线段能够依次包含所有的 mm 个点,问线段移动总距离的最小值。

          1n,m2×105, 0li,ri1091 \le n,m \le 2 \times 10^5,~0 \le l_i,r_i \le 10^9

          Solution

          Solution

          由于 lipli+lenl_i \le p \le l_i + lenplen+1lipp - len + 1 \le l_i \le p 相同,因此在固定询问线段长度 lenlen 的情况下,可以将原问题中的询问线段变为位置在 lil_i 上的单点,mm 个点变为 [plen+1, p][p - len + 1,~p] 的线段,问题即转换为求移动该点使其依次经过每个区间的最短总距离。

          结论 1:在一种移动方案中,若 i1i - 1 时刻向 ii 时刻移动的方向与 ii 时刻向 i+1i + 1 时刻移动的方向相同,则 ii 时刻的限制可以无视。

          证明:令 ii 时刻点所在位置为 pip_i,以向右移动为例则若条件满足则说明 pi1<pi<pi+1p_{i - 1} < p_i < p_{i + 1}。固定 pi1p_{i - 1}pi+1p_{i + 1} 时所有在该两点间的移动方案总会经过 pip_i,在经过 pip_i 时满足 ii 时刻限制即可。

          结论 2:若两个相邻限制线段 [li, ri][l_i,~r_i][li+1, ri+1][l_{i + 1},~r_{i + 1}] 有交,则这两条线段的限制条件与一条 [max(li, li+1), min(ri, ri+1)][\max(l_i,~l_{i + 1}),~\min(r_i,~r_{i + 1})] 线段相同。

          证明:pip_ipi+1p_{i + 1} 移动的过程中必定会经过他们交线段上的至少一个点,因此满足两条线段限制条件的方案必定满足交线段的限制条件。所有满足交线段限制条件的方案显然满足 ii 时刻和 i+1i + 1 时刻的限制,因此满足交线段限制条件的方案必定满足原来的两条线段的限制条件。

          当我们固定询问区间长度 lenlen 时,通过结论 2 的约束,我们可以使得最终限制条件中任意两条相邻线段均不交。因此我们能够确定每一条线段(除了最后一条),该线段与下一条线段之间的移动方向。

          结论 3:对于线段 ii,若其到线段 i+1i + 1 的移动方向为左,则线段 ii 的限制条件与 [li, li][l_i,~l_i] 相同。

          证明显然,根据贪心,离下一条线段最近的点必然不劣。

          根据结论 3,我们可以把所有线段限制缩为点,问题转化为:询问一点与 mm 个给定点依次相交的移动路径和。我们令第 ii 个限制为 limilim_i

          根据结论 1,我们发现若出现 limi1<limi<limi+1lim_{i - 1} < lim_i < lim_{i + 1} 的情况,则 limilim_i 将不会起约束作用。我们按上述限制删除无用限制后,发现限制总是满足: limi1<limi>limi+1lim_{i - 1} < lim_i > lim_{i + 1}limi1>limi<limi+1lim_{i - 1} > lim_i < lim_{i + 1}。此时询问 qq 的答案即为 lim1lq+i=1m1limilimi+1|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} |

          在固定 lenlen 的情况下我们已经能够求解原问题了,考虑在不固定 lenlen 时我们应该怎么做。我们考虑将所有询问离线后按照 lenlen 排序,从小到达枚举 lenlen 的同时维护限制条件下对应的答案。

          我们可以将所有 limlim 分为左右两半,满足 limi1>limi<limi+1lim_{i - 1} > lim_i < lim_{i + 1} 的为左点,满足 limi1<limi>limi+1lim_{i - 1} < lim_i > lim_{i + 1} 的为右点。最终移动路径上的点一定为左右点相邻。所有的左点为原区间的右端点,所有的右点为原区间的左端点。由于原区间为 [plen+1, p][p - len + 1,~p],在 lenlen 增大时左端点会向左移动,即所有右点在 lenlen 增大 11 时会向左移动 11。因此在询问的 lenlen 增大时我们只要给全局所有的右点通过懒标记整体向左移即可。

          但是由于右点向左移动最终会与左点相交,相交后根据结论 2 我们需要删除相交的两个点中的一个,删除一个点后会出现两个同类点相邻的情况,令未删除的点为 xx。当 xx 为第一个限制或是最后一个限制时令 xx 从左点变为右点或是从右点变为左点,xx 不为第一个或最后一个时删除 xx 因为其值在 x1x - 1x+1x + 1 之间。上述操作完后即可重新回到正常状态。

          令相邻两限制间的距离为他们初始时刻的距离,使用 setset 维护所有相邻两限制间的距离,处理时间 timtim 时将所有距离不超过 timtim 的限制按照上述操作处理即可。由于每个时刻相邻两限制间的距离都会减一,因此最终答案即为 lim1lq+i=1m1limilimi+1(m1)×tim|lim_1 - l_q| + \sum_{i = 1}^{m - 1} | lim_i - lim_{i + 1} | - (m - 1) \times tim。全局维护相邻限制距离和即可。

          需要注意的是当只剩下一个限制时,由于不存在所谓“下一步移动方向”,随时间推移该点会逐渐展开为线段。

          时间复杂度 O(nlogn)O(n \log n),常数较大。

          Code

          View on GitHub

          /**
           * @file 4249.cpp
           * @author Macesuted (i@macesuted.moe)
           * @date 2022-03-25
           *
           * @copyright Copyright (c) 2022
           * @brief
           *      My Tutorial: https://macesuted.moe/article/bzoj4249
           *
           */
          
          #include <bits/stdc++.h>
          using namespace std;
          
          namespace IO {
          const int SIZE = 1 << 20;
          char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
          char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
          void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
          void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
          char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
          char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
          void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
          template <typename T>
          T read(void) {
              T x = 0, f = +1;
              char c = getch();
              while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
              while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
              return x * f;
          }
          template <typename T>
          void write(T x) {
              if (!x) putch('0');
              if (x < 0) putch('-'), x = -x;
              int top = 0;
              while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
              while (top) putch(stack[--top]);
              return;
          }
          string getstr(const string& suf = "") {
              string s = suf;
              while (isspace(buftop())) getch();
              while (Il != Ir) {
                  char* p = Il;
                  while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
                  s.append(p, Il);
                  if (Il < Ir) break;
                  fill();
              }
              return s;
          }
          void putstr(string str, int begin = 0, int end = -1) {
              if (end == -1) end = str.size();
              for (int i = begin; i < end; i++) putch(str[i]);
              return;
          }
          struct Flusher_ {
              ~Flusher_() { flush(); }
          } io_flusher_;
          }  // namespace IO
          using IO::getch;
          using IO::getstr;
          using IO::putch;
          using IO::putstr;
          using IO::read;
          using IO::write;
          
          bool mem1;
          
          #define maxn 200005
          
          typedef pair<int, int> pii;
          
          set<pii> S, Sd;
          map<int, vector<pii>> ques;
          int a[maxn];
          long long ans[maxn], answer = 0;
          
          template <typename T>
          T dec(T a) {
              return --a;
          }
          template <typename T>
          T inc(T a) {
              return ++a;
          }
          void insert(set<pii>::iterator p) {
              return answer += abs(p->second - inc(p)->second), Sd.emplace(abs(p->second - inc(p)->second), p->first), void();
          }
          void erase(set<pii>::iterator p) {
              return answer -= abs(p->second - inc(p)->second), Sd.erase({abs(p->second - inc(p)->second), p->first}), void();
          }
          
          void check(pii x, int tim) {
              auto p = S.find(x);
              if (p == S.begin() && p == dec(S.end())) return;
              if (p == S.begin()) {
                  if (p->second == inc(p)->second) return S.erase(p), void();
                  if (inc(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first;
                  return insert(p);
              }
              if (p == dec(S.end())) {
                  if (p->second == dec(p)->second) return S.erase(p), void();
                  if (dec(p)->second < p->second) S.erase(p), p = S.emplace(x.first, x.second + tim).first;
                  return insert(dec(p));
              }
              return insert(--S.erase(p));
          }
          
          void solve(void) {
              int n = read<int>(), m = read<int>();
              for (int i = 1; i <= n; i++) {
                  int l = read<int>(), r = read<int>();
                  ques[r - l].emplace_back(l, i);
              }
              for (int i = 1; i <= m; i++) S.emplace(i, a[i] = read<int>());
              for (auto i = ++S.begin(); inc(i) != S.end(); i++)
                  if ((dec(i)->second < i->second) == (i->second < inc(i)->second) || dec(i)->second == i->second ||
                      i->second == inc(i)->second)
                      i = --S.erase(i);
              for (auto i = S.begin(); inc(i) != S.end(); i++)
                  Sd.emplace(abs(i->second - inc(i)->second), i->first), answer += abs(i->second - inc(i)->second);
              int last = 0;
              while (!Sd.empty()) {
                  int tim = Sd.begin()->first, ip = Sd.begin()->second;
                  Sd.erase(Sd.begin());
                  if (tim != last)
                      for (auto i = ques.begin(); i != ques.end() && i->first < tim; i = ques.erase(i)) {
                          int t = S.begin()->second;
                          if (S.begin()->second > inc(S.begin())->second) t -= i->first;
                          for (auto j : i->second) ans[j.second] = answer + abs(t - j.first) - 1LL * ((int)S.size() - 1) * i->first;
                      }
                  last = tim;
                  auto p = S.lower_bound({ip, 0}), q = inc(p);
                  erase(p);
                  if (p->second > q->second) {
                      if (p != S.begin()) erase(dec(p));
                      q = S.erase(p);
                      if (q != dec(S.end())) erase(q);
                      check(*q, tim);
                  } else {
                      if (q != dec(S.end())) erase(q);
                      p = --S.erase(q);
                      if (p != S.begin()) erase(dec(p));
                      check(*p, tim);
                  }
              }
              for (auto i : ques)
                  for (auto j : i.second)
                      if (S.begin()->second - (i.first - last) <= j.first && j.first <= S.begin()->second)
                          ans[j.second] = 0;
                      else
                          ans[j.second] = min(abs(S.begin()->second - j.first), abs(S.begin()->second - (i.first - last) - j.first));
              for (int i = 1; i <= n; i++) write(ans[i]), putch('\n');
              return;
          }
          
          bool mem2;
          
          int main() {
              ios::sync_with_stdio(false);
          #ifdef MACESUTED
              cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
          #endif
          
              int _ = 1;
              while (_--) solve();
          
          #ifdef MACESUTED
              cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
          #endif
              return 0;
          }
          
          • @ 2022-3-25 7:22:15

            #025 2022.3.25

            标签:数据结构,线段树,可持久化,珂朵莉树。

            Statement

            nn 匹魔法小马,第 ii 匹小马在初始时具有 sis_i 的魔法值,每秒钟回复 rir_i 魔法值,魔法值上限为 mim_i

            你会进行 qq 次操作,每次操作在 tit_i 时刻会将 lil_irir_i 范围内的所有小马的魔法值吸走,吸走后此范围内小马魔法值归零,请你求出每次操作吸走的魔法值总和。

            1n,q1051 \le n,q \le 10^5

            Solution

            Solution

            对于有区间归零操作的问题,我们的常用方法是记录每个位置上次被清零的时间。考虑一个最简单的简化问题版本:所有操作均为全局操作(即 li=1, ri=nl_i = 1,~r_i = n)。此时每次询问时所有位置离上次清零的时间均相同,令该时间为 tt,我们发现所有 mirit\frac {m_i} {r_i} \le t 的小马的魔法值都会达到上限 mim_i,其他小马的魔法值则为 ri×tr_i \times t。因此我们可以将所有小马按照 miri\frac {m_i} {r_i} 排序,二分找到序列中 t\le t 的最大位置 pp,则 1ipmi+t×(p<inri)\sum_{1 \le i \le p} m_i + t \times (\sum_{p < i \le n} r_i) 即为答案。

            考虑在清零操作为全局而询问操作为区间时该怎么做,即想要求得 i[l, r], miriti \in [l,~r],~\frac {m_i} {r_i} \le t 的所有元素的 mim_i 和与 rir_i 和。经典的静态二维数点问题,为降低复杂度可以在 miri\frac {m_i} {r_i} 一维上进行可持久化。具体的,将所有小马的 miri\frac {m_i} {r_i} 排序,可持久化线段树的第 ii 个版本中插入排序后的前 ii 个元素。则二维数点问题转换为在排序后的数组上二分找到最大的 t\le t 的位置,在其对应的版本上询问 [l, r][l,~r] 区间信息,复杂度 O(logn)O(\log n)

            再考虑原问题,若全局的清零时间不同时应该怎么做。发现使用珂朵莉树维护每个连续清零时间相同的连续段即可。因为每次修改后会将区间内的所有元素的清零时间归零,每次询问时暴力扫描的每一块在询问后会被合并为一块,因此全局暴力扫描的时间复杂度为珂朵莉上块数的总和,而每次操作最多只会新建两个块,因此复杂度得以保证。对于珂朵莉树上的每个连续段,由于段内清零时间相同,做上述的可持久化线段树上查询即可。

            另外,一个比较好的处理初始值 sis_i 的方法是将第 ii 个小马的初始上次清零时间设为 siri- \frac {s_i} {r_i}

            总时间复杂度 O((n+q)logn)O((n + q) \log n)

            Code

            View on GitHub

            /**
             * @file 453E.cpp
             * @author Macesuted (i@macesuted.moe)
             * @date 2022-03-20
             *
             * @copyright Copyright (c) 2022
             *
             */
            
            #include <bits/stdc++.h>
            using namespace std;
            
            namespace IO {
            const int SIZE = 1 << 20;
            char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
            char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
            void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
            void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
            char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
            char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
            void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
            template <typename T>
            T read(void) {
                T x = 0, f = +1;
                char c = getch();
                while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
                while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
                return x * f;
            }
            template <typename T>
            void write(T x) {
                if (!x) putch('0');
                if (x < 0) putch('-'), x = -x;
                int top = 0;
                while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
                while (top) putch(stack[--top]);
                return;
            }
            string getstr(const string& suf = "") {
                string s = suf;
                while (isspace(buftop())) getch();
                while (Il != Ir) {
                    char* p = Il;
                    while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
                    s.append(p, Il);
                    if (Il < Ir) break;
                    fill();
                }
                return s;
            }
            void putstr(string str, int begin = 0, int end = -1) {
                if (end == -1) end = str.size();
                for (int i = begin; i < end; i++) putch(str[i]);
                return;
            }
            struct Flusher_ {
                ~Flusher_() { flush(); }
            } io_flusher_;
            }  // namespace IO
            using IO::getch;
            using IO::getstr;
            using IO::putch;
            using IO::putstr;
            using IO::read;
            using IO::write;
            
            bool mem1;
            
            #define maxn 100005
            
            typedef pair<long long, long long> pll;
            
            class SegmentTree {
               private:
                struct Node {
                    Node *l, *r;
                    long long sumR, sumM;
                    Node(void) { l = r = NULL, sumR = sumM = 0; }
                };
            
                vector<Node*> roots;
                int n;
            
                Node* newRoot(void) { return roots.push_back(roots.back()), roots.back(); }
                void exist(Node*& p, Node* o) {
                    if (p != o && p != NULL) return;
                    return p = new Node(), *p = *o, void();
                }
                void pushUp(Node* p) {
                    p->sumR = p->sumM = 0;
                    if (p->l != NULL) p->sumR += p->l->sumR, p->sumM += p->l->sumM;
                    if (p->r != NULL) p->sumR += p->r->sumR, p->sumM += p->r->sumM;
                    return;
                }
                pll merge(pll a, pll b) { return {a.first + b.first, a.second + b.second}; }
                void insert(Node*& p, Node* o, int l, int r, int qp, int vr, int vm) {
                    if (o == NULL) p = o = new Node();
                    exist(p, o);
                    if (l == r) return p->sumR = vr, p->sumM = vm, void();
                    int mid = (l + r) >> 1;
                    qp <= mid ? insert(p->l, o->l, l, mid, qp, vr, vm) : insert(p->r, o->r, mid + 1, r, qp, vr, vm);
                    return pushUp(p);
                }
                pll query(Node* p, int l, int r, int ql, int qr) {
                    if (p == NULL) return {0, 0};
                    if (ql <= l && r <= qr) return {p->sumR, p->sumM};
                    int mid = (l + r) >> 1;
                    if (qr <= mid) return query(p->l, l, mid, ql, qr);
                    if (ql > mid) return query(p->r, mid + 1, r, ql, qr);
                    return merge(query(p->l, l, mid, ql, qr), query(p->r, mid + 1, r, ql, qr));
                }
            
               public:
                SegmentTree(void) { roots.push_back(NULL); }
                void resize(int _n) { return n = _n, void(); }
                void insert(int p, int r, int m) { return newRoot(), insert(roots.back(), roots[(int)roots.size() - 2], 1, n, p, r, m); }
                pll query(int ver, int l, int r) { return query(roots[ver], 1, n, l, r); }
            } ST;
            
            pair<double, int> t[maxn];
            long long rsum[maxn];
            
            class OldDriverTree {
               private:
                struct Node {
                    int l, r;
                    double tim;
                    bool operator<(const Node& oth) const { return this->l < oth.l; }
                };
            
                set<Node> S;
                int n;
            
                void split(Node p, int v) {
                    S.erase(p), S.insert({p.l, v, p.tim});
                    if (v < p.r) S.insert({v + 1, p.r, p.tim});
                    return;
                }
            
               public:
                void build(int _n, double b[]) {
                    n = _n;
                    for (int l = 1, r; l <= n; l = r + 1) {
                        r = l;
                        while (r < n && b[r + 1] == b[r]) r++;
                        S.insert({l, r, b[l]});
                    }
                    return;
                }
                long long query(int T, int l, int r) {
                    auto x = --S.lower_bound({l + 1, 0, 0});
                    if (x->l != l) split(*x, l - 1);
                    x = --S.lower_bound({r + 1, 0, 0});
                    if (x->r != r) split(*x, r);
                    long long ans = 0;
                    for (auto i = S.lower_bound({l, 0, 0}); i != S.end() && i->r <= r; i = S.erase(i)) {
                        double tim = T - i->tim;
                        int p = lower_bound(t + 1, t + n + 1, make_pair(tim, 0)) - t;
                        pll ret = ST.query(p - 1, i->l, i->r);
                        ans += ret.second + (long long)((rsum[i->r] - rsum[i->l - 1] - ret.first) * tim + 0.5);
                    }
                    S.insert({l, r, (double)T});
                    return ans;
                }
            } ODT;
            
            int s[maxn], m[maxn], r[maxn];
            double b[maxn];
            
            set<pll> S;
            
            void solve(void) {
                int n = read<int>();
                for (int i = 1; i <= n; i++) {
                    s[i] = read<int>(), m[i] = read<int>(), r[i] = read<int>();
                    if (r[i])
                        t[i] = {1. * m[i] / r[i], i}, b[i] = -1. * s[i] / r[i];
                    else
                        S.emplace(i, s[i]), t[i] = {1e18, i}, b[i] = 0;
                }
                for (int i = 1; i <= n; i++) rsum[i] = rsum[i - 1] + r[i];
                sort(t + 1, t + n + 1);
                ST.resize(n), ODT.build(n, b);
                for (int i = 1; i <= n; i++) ST.insert(t[i].second, r[t[i].second], m[t[i].second]);
                int q = read<int>();
                while (q--) {
                    int t = read<int>(), l = read<int>(), r = read<int>();
                    long long ans = ODT.query(t, l, r);
                    for (auto i = S.lower_bound({l, 0}); i != S.end() && i->first <= r; i = S.erase(i)) ans += i->second;
                    write(ans), putch('\n');
                }
                return;
            }
            
            bool mem2;
            
            int main() {
                ios::sync_with_stdio(false);
            #ifdef MACESUTED
                cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
            #endif
            
                int _ = 1;
                while (_--) solve();
            
            #ifdef MACESUTED
                cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
            #endif
                return 0;
            }
            
            • @ 2022-3-22 7:36:02

              #024 2022.3.22

              标签:树链剖分,扫描线。

              Statement

              给出一个 nn 个点的树。现在有 mm 个人,每个人在 tit_i 时刻出现在树上,以每秒 cic_i 条边的速度从 uiu_i 走到 viv_i。请你求出最早的有两人相遇的时间,没有则输出 1-1

              1n,m105, 0ti1041 \le n,m \le 10^5,~0 \le t_i \le 10^4

              Solution

              Solution

              考虑树为一条链时怎么做。发现若以时间为横坐标,每个人所处的在链上的位置为纵坐标,每个人可以被表示为一条线段,问题即为求线段交点横坐标最小值。在横坐标上做扫描线,维护一个 set 存放当前时刻所有出现的线段即可。相交线段在相交前一定相邻,每次插入删除时对相邻两线段求交点并于答案取较小值即可。关于 set 如何按照当前横坐标上每条线段对应的纵坐标排序,重载小于号令其按照当前时刻线段横坐标大小排序即可。虽然随扫描线推移过程原来为小于关系的两条线段不一定一直小于,但是这样打乱相对顺序的情况表示其已经出现了交点,不需要继续向后做扫描线了。因此直接按照当前时刻横坐标来比对是正确的。

              至于树上情况应该怎么做,在树上进行树链剖分后,将每一个人的行动轨迹拆分到每条路径上的轻重链上即可。最终对每条轻重链执行上述操作,将所得的每条链的答案取最小值即可得到答案。

              Code

              View on GitHub

              /**
               * @file 704E.cpp
               * @author Macesuted (i@macesuted.moe)
               * @date 2022-03-20
               *
               * @copyright Copyright (c) 2022
               * @brief
               *      My Tutorial: https://macesuted.moe/article/cf704e
               *
               */
              
              #include <bits/stdc++.h>
              using namespace std;
              
              namespace IO {
              const int SIZE = 1 << 20;
              char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
              char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
              void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
              void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
              char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
              char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
              void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
              template <typename T>
              T read(void) {
                  T x = 0, f = +1;
                  char c = getch();
                  while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
                  while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
                  return x * f;
              }
              template <typename T>
              void write(T x) {
                  if (!x) putch('0');
                  if (x < 0) putch('-'), x = -x;
                  int top = 0;
                  while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
                  while (top) putch(stack[--top]);
                  return;
              }
              string getstr(const string& suf = "") {
                  string s = suf;
                  while (isspace(buftop())) getch();
                  while (Il != Ir) {
                      char* p = Il;
                      while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
                      s.append(p, Il);
                      if (Il < Ir) break;
                      fill();
                  }
                  return s;
              }
              void putstr(string str, int begin = 0, int end = -1) {
                  if (end == -1) end = str.size();
                  for (int i = begin; i < end; i++) putch(str[i]);
                  return;
              }
              struct Flusher_ {
                  ~Flusher_() { flush(); }
              } io_flusher_;
              }  // namespace IO
              using IO::getch;
              using IO::getstr;
              using IO::putch;
              using IO::putstr;
              using IO::read;
              using IO::write;
              
              bool mem1;
              
              #define maxn 100005
              #define eps 1e-10
              
              typedef pair<int, int> pii;
              typedef tuple<int, long double, int, long double> tidid;
              
              long double TIM, ans = numeric_limits<long double>::max();
              
              struct comp {
                  long double getPos(const tidid& a) const {
                      return get<1>(a) == get<3>(a) ? get<0>(a)
                                                    : get<0>(a) + (TIM - get<1>(a)) * (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a));
                  }
                  bool operator()(const tidid& a, const tidid& b) const { return getPos(a) < getPos(b); }
              };
              
              vector<vector<int>> graph;
              int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
              vector<tidid> heav[maxn], ligh[maxn];
              
              void dfs1(int p) {
                  siz[p] = 1;
                  for (auto i : graph[p])
                      if (i != fa[p]) {
                          fa[i] = p, dep[i] = dep[p] + 1, dfs1(i), siz[p] += siz[i];
                          if (!son[p] || siz[i] > siz[son[p]]) son[p] = i;
                      }
                  return;
              }
              void dfs2(int p, int top_) {
                  top[p] = top_;
                  if (son[p]) dfs2(son[p], top_);
                  for (auto i : graph[p])
                      if (i != fa[p] && i != son[p]) dfs2(i, i);
                  return;
              }
              int LCA(int x, int y) {
                  while (top[x] != top[y]) {
                      if (dep[top[x]] < dep[top[y]]) swap(x, y);
                      x = fa[top[x]];
                  }
                  return dep[x] < dep[y] ? x : y;
              }
              void calcCross(tidid a, tidid b) {
                  long double ak = (get<2>(a) - get<0>(a)) / (get<3>(a) - get<1>(a)), bk = (get<2>(b) - get<0>(b)) / (get<3>(b) - get<1>(b)),
                              ad = get<0>(a) - get<1>(a) * ak, bd = get<0>(b) - get<1>(b) * bk;
                  if ((ad < bd) != (ad + ak * TIM < bd + bk * TIM)) return;
                  long double ret = (ad - bd) / (bk - ak);
                  if (ret < max(get<1>(a), get<1>(b)) - eps || ret > min(get<3>(a), get<3>(b)) + eps) return;
                  return ans = min(ans, ret), void();
              }
              void calc(vector<tidid>& a) {
                  static vector<long double> pos;
                  static vector<vector<tidid>> in, out;
                  pos.clear(), pos.reserve(2 * a.size()), in.clear(), out.clear();
                  for (auto i : a) pos.push_back(get<1>(i)), pos.push_back(get<3>(i));
                  sort(pos.begin(), pos.end()), pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
                  in.resize(pos.size()), out.resize(pos.size());
                  for (auto i : a)
                      in[lower_bound(pos.begin(), pos.end(), get<1>(i)) - pos.begin()].push_back(i),
                          out[lower_bound(pos.begin(), pos.end(), get<3>(i)) - pos.begin()].push_back(i);
                  static set<tidid, comp> S1;
                  S1.clear();
                  for (int i = 0; i < (int)pos.size(); i++) {
                      TIM = pos[i];
                      if (TIM > ans) return;
                      for (auto j : in[i]) {
                          auto ret = S1.emplace(j);
                          if (!ret.second) return ans = min(ans, pos[i]), void();
                          auto pl = ret.first, pr = pl;
                          if (pl != S1.begin()) calcCross(*--pl, j);
                          if (++pr != S1.end()) calcCross(j, *pr);
                      }
                      for (auto j : out[i]) {
                          auto p2 = S1.erase(S1.find(j)), p1 = p2;
                          if (p1 != S1.begin() && p2 != S1.end()) calcCross(*--p1, *p2);
                      }
                  }
                  return;
              }
              
              void solve(void) {
                  int n = read<int>(), m = read<int>();
                  graph.resize(n + 1);
                  for (int i = 1; i < n; i++) {
                      int x = read<int>(), y = read<int>();
                      graph[x].push_back(y), graph[y].push_back(x);
                  }
                  dfs1(1), dfs2(1, 1);
                  for (int i = 1; i <= m; i++) {
                      long double tim = read<int>(), c = read<int>();
                      int x = read<int>(), y = read<int>(), t = LCA(x, y);
                      while (top[x] != top[t]) {
                          heav[top[x]].emplace_back(x, tim, top[x], tim + (dep[x] - dep[top[x]]) / c), tim += (dep[x] - dep[top[x]]) / c,
                              x = top[x];
                          ligh[x].emplace_back(x, tim, fa[x], tim + 1 / c), tim += 1 / c, x = fa[x];
                      }
                      static stack<pii> cache;
                      while (!cache.empty()) cache.pop();
                      while (top[y] != top[t]) cache.emplace(y, top[y]), y = fa[top[y]];
                      heav[top[y]].emplace_back(x, tim, y, tim + abs(dep[x] - dep[y]) / c), tim += abs(dep[x] - dep[y]) / c;
                      while (!cache.empty()) {
                          pii p = cache.top();
                          cache.pop();
                          ligh[p.second].emplace_back(fa[p.second], tim, p.second, tim + 1 / c), tim += 1 / c;
                          heav[p.second].emplace_back(p.second, tim, p.first, tim + (dep[p.first] - dep[p.second]) / c),
                              tim += (dep[p.first] - dep[p.second]) / c;
                      }
                  }
                  for (int i = 1; i <= n; i++) {
                      for (auto& j : heav[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 1, get<2>(j) = dep[get<2>(j)] - dep[i] + 1;
                      for (auto& j : ligh[i]) get<0>(j) = dep[get<0>(j)] - dep[i] + 2, get<2>(j) = dep[get<2>(j)] - dep[i] + 2;
                      calc(heav[i]), calc(ligh[i]);
                  }
                  if (ans == numeric_limits<long double>::max()) return putstr("-1\n");
                  cout << setiosflags(ios::fixed) << setprecision(30) << ans << endl;
                  return;
              }
              
              bool mem2;
              
              int main() {
                  ios::sync_with_stdio(false);
              #ifdef MACESUTED
                  cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
              #endif
              
                  int _ = 1;
                  while (_--) solve();
              
              #ifdef MACESUTED
                  cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
              #endif
                  return 0;
              }
              
              • @ 2022-3-21 7:27:08

                #023 2022.3.21

                标签:数据结构,线段树。

                Statement

                给定一个长为 nn 的序列 aa,需要实现 mm 次操作:

                • 1 l r x: 表示将区间 [l, r][l,~r] 中所有 >x>x 的元素减去 xx
                • 2 l r: 表示询问区间 [l, r][l,~r] 的和,最小值,最大值。

                强制在线,n, m5×105, ai109n,~m \le 5 \times 10^5,~a_i \le 10^9

                Solution

                Solution

                考虑以 22 进制进行值域分块,第 ii 块开动态开点线段树存储所有满足 ai[2i, 2i+1)a_i \in [2^i,~2^{i+1}) 的位置的信息。

                考虑对于 11 操作,我们枚举每一个值域块,将该块内下标在 [l, r][l,~r] 之间的元素拿出,进行判断:

                • 若该块所有元素值均 >x>x: 对这些元素打上 x-x 标记即可。
                • 若该块所有元素值均 x\le x: 不进行任何操作。
                • 若不满足上述两个条件: 在线段树上向子树递归进行修改操作。

                考虑分析此处暴力递归的时间复杂度,容易发现在某块内每次成功的修改都会让被修改元素减少至少一半。显然单个元素最多被修改 log2ai\log_2 a_i 次,因此全局总共花在暴力递归上的复杂度为 O(nlog2ai)O(n \log_2 a_i)

                在每次修改后,一些 aia_i 值减小后可能会因为过小而需要被分配到编号更小的块中,我们可以在线段树每个节点上维护子树最小值,每次修改完成后暴力二分找出过小的位置,将其从当前块线段树上暴力拆出,插入到更小编号的块的线段树内。考虑此操作总时间复杂度,因为一共只有 log2ai\log_2 a_i 个块而每次结点只会从当前块到编号更小的块,因此每个元素最多只会在块间移动 log2ai\log_2 a_i 次,所以花在此操作上的全局总时间复杂度为 O(nlog2ailog2n)O(n \log_2 a_i \log_2 n)

                对于 2 操作,我们只要将每块内的 [l, r][l,~r] 部分答案取出合并起来就可以了。

                此时总时间复杂度 O(nlog2nlog2ai)O(n \log_2 n \log_2 a_i),空间复杂度 O(nlog2ai)O(n \log_2 a_i)

                我们发现这样的空间复杂度不足以通过此题,我们考虑线段树底层以 log2ai\log_2 a_i 块长分块,则每棵线段树叶子节点数量为 nlog2ai\frac {n} {\log_2 a_i},空间复杂度降为 O(n)O(n),可以通过此题。

                由于此题较卡常,可以考虑根据代码运行情况调整分块的进制和线段树底层分块块长。

                Code

                本人代码使用指针版动态开点线段树,线段树底层块内使用链表储存,14 进制值域分块,线段树底层块长 500(由于常数比较大,小块长一直 TLE 一个点,但是这个接近 n\sqrt n 的块长出乎意料地跑得飞快)。

                View On Github

                /**
                 * @author Macesuted (i@macesuted.moe)
                 * @copyright Copyright (c) 2021
                 * @brief
                 *      My solution: https://www.macesuted.cn/article/lg7447/
                 */
                
                #include <bits/stdc++.h>
                using namespace std;
                
                namespace io {
                #define SIZE (1 << 20)
                char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
                int f, qr;
                inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
                inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
                inline void putch(char x) {
                    *oS++ = x;
                    if (oS == oT) flush();
                    return;
                }
                string getstr(void) {
                    string s = "";
                    char c = getch();
                    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
                    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
                    return s;
                }
                void putstr(string str, int begin = 0, int end = -1) {
                    if (end == -1) end = str.size();
                    for (register int i = begin; i < end; i++) putch(str[i]);
                    return;
                }
                template <typename T>
                inline T read() {
                    register T x = 0;
                    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                        if (c == '-') f = -1;
                    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
                    return x * f;
                }
                template <typename T>
                inline void write(const T& t) {
                    register T x = t;
                    if (!x) putch('0');
                    if (x < 0) putch('-'), x = -x;
                    while (x) qu[++qr] = x % 10 + '0', x /= 10;
                    while (qr) putch(qu[qr--]);
                    return;
                }
                struct Flusher_ {
                    ~Flusher_() { flush(); }
                } io_flusher_;
                }  // namespace io
                using io::getch;
                using io::getstr;
                using io::putch;
                using io::putstr;
                using io::read;
                using io::write;
                
                #define maxn 500005
                #define blockLen 500
                
                typedef pair<int, int> pii;
                
                vector<pii> empty;
                
                class SegmentTree {
                   public:
                    struct AnsType {
                        long long sum;
                        int minVal, maxVal;
                        AnsType(void) { sum = 0, minVal = 0x3f3f3f3f, maxVal = 0; }
                        AnsType(long long _sum, int _minVal, int _maxVal) { sum = _sum, minVal = _minVal, maxVal = _maxVal; }
                        inline AnsType operator+(const AnsType& oth) const {
                            return (AnsType){sum + oth.sum, min(minVal, oth.minVal), max(maxVal, oth.maxVal)};
                        }
                    };
                
                   private:
                    struct Node {
                        int minVal, maxVal, size;
                        long long sum, lazy;
                        Node *l, *r;
                        vector<pii> rec;
                        Node(void) { l = r = NULL, minVal = 0x3f3f3f3f, maxVal = sum = lazy = size = 0; }
                    };
                
                    Node* root;
                    int n;
                
                    void update(Node* p, int l, int r, long long delta) {
                        if (r - l + 1 <= blockLen) {
                            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++) i->second -= delta;
                            return recalc(p, l, r);
                        }
                        p->lazy += delta, p->minVal -= delta, p->maxVal -= delta, p->sum -= p->size * delta;
                        return;
                    }
                    void recalc(Node* p, int l, int r) {
                        p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = p->rec.size();
                        for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                            p->sum += i->second, p->minVal = min(p->minVal, i->second), p->maxVal = max(p->maxVal, i->second);
                        return;
                    }
                    void pushDown(Node* p, int l, int r) {
                        if (p == NULL) return;
                        if (!p->lazy) return;
                        int mid = (l + r) >> 1;
                        if (p->l != NULL) update(p->l, l, mid, p->lazy);
                        if (p->r != NULL) update(p->r, mid + 1, r, p->lazy);
                        p->lazy = 0;
                        return;
                    }
                    inline void pushUp(Node* p) {
                        p->minVal = 0x3f3f3f3f, p->maxVal = 0, p->sum = 0, p->size = 0;
                        if (p->l != NULL)
                            p->minVal = min(p->minVal, p->l->minVal), p->maxVal = max(p->maxVal, p->l->maxVal),
                            p->sum += p->l->sum, p->size += p->l->size;
                        if (p->r != NULL)
                            p->minVal = min(p->minVal, p->r->minVal), p->maxVal = max(p->maxVal, p->r->maxVal),
                            p->sum += p->r->sum, p->size += p->r->size;
                        return;
                    }
                    void insert(Node*& p, int l, int r, int qp, int val) {
                        if (p == NULL) p = new Node();
                        if (r - l + 1 <= blockLen) {
                            bool find = false;
                            for (vector<pii>::iterator i = p->rec.begin(); !find && i != p->rec.end(); i++)
                                if (i->first == qp) i->second = val, find = true;
                            if (!find) p->rec.push_back((pii){qp, val});
                            return recalc(p, l, r);
                        }
                        pushDown(p, l, r);
                        int mid = (l + r) >> 1;
                        qp <= mid ? insert(p->l, l, mid, qp, val) : insert(p->r, mid + 1, r, qp, val);
                        return pushUp(p);
                    }
                    void update(Node* p, int l, int r, int ql, int qr, long long val) {
                        if (p == NULL) return;
                        if (p->maxVal <= val) return;
                        if (ql <= l && r <= qr && p->minVal > val) return update(p, l, r, val);
                        if (r - l + 1 <= blockLen) {
                            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                                if (ql <= i->first && i->first <= qr && i->second > val) i->second -= val;
                            return recalc(p, l, r);
                        }
                        pushDown(p, l, r);
                        int mid = (l + r) >> 1;
                        if (ql <= mid) update(p->l, l, mid, ql, qr, val);
                        if (qr > mid) update(p->r, mid + 1, r, ql, qr, val);
                        return pushUp(p);
                    }
                    AnsType getAns(Node* p, int l, int r, int ql, int qr) {
                        if (p == NULL) return (AnsType){};
                        if (ql <= l && r <= qr) return (AnsType){p->sum, p->minVal, p->maxVal};
                        if (r - l + 1 <= blockLen) {
                            AnsType ans = (AnsType){0, 0x3f3f3f3f, 0};
                            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                                if (ql <= i->first && i->first <= qr)
                                    ans.sum += i->second, ans.minVal = min(ans.minVal, i->second), ans.maxVal = max(ans.maxVal, i->second);
                            return ans;
                        }
                        pushDown(p, l, r);
                        int mid = (l + r) >> 1;
                        AnsType answer;
                        if (ql <= mid) answer = answer + getAns(p->l, l, mid, ql, qr);
                        if (qr > mid) answer = answer + getAns(p->r, mid + 1, r, ql, qr);
                        return answer;
                    }
                    void findEmpty(Node*& p, int l, int r, int limit) {
                        if (p == NULL) return;
                        if (p->minVal >= limit) return;
                        if (r - l + 1 <= blockLen) {
                            static vector<pii> cache;
                            cache.clear();
                            for (vector<pii>::iterator i = p->rec.begin(); i != p->rec.end(); i++)
                                (i->second < limit ? empty : cache).push_back(*i);
                            p->rec = cache;
                            recalc(p, l, r);
                            if (p->size == 0) delete p, p = NULL;
                            return;
                        }
                        pushDown(p, l, r);
                        int mid = (l + r) >> 1;
                        findEmpty(p->l, l, mid, limit), findEmpty(p->r, mid + 1, r, limit);
                        pushUp(p);
                        if (p->size == 0) delete p, p = NULL;
                        return;
                    }
                
                   public:
                    SegmentTree(void) { root = NULL; }
                    inline void resize(int _n) { return n = _n, void(); }
                    inline void insert(int p, int val) { return insert(root, 1, n, p, val); }
                    inline void update(int l, int r, long long delta) { return update(root, 1, n, l, r, delta); }
                    inline AnsType getAns(int l, int r) { return getAns(root, 1, n, l, r); }
                    inline void findEmpty(int limit) { return findEmpty(root, 1, n, limit); }
                };
                
                SegmentTree tree[8];
                long long pow14[8];
                
                int log14(int x) {
                    int t = 0;
                    while (t < 7 && pow14[t + 1] <= x) t++;
                    return t;
                }
                
                int main() {
                    pow14[0] = 1;
                    for (register int i = 1; i < 8; i++) pow14[i] = pow14[i - 1] * 14;
                    int n = read<int>(), m = read<int>();
                    for (register int i = 0; i < 8; i++) tree[i].resize(n);
                    for (register int i = 1, t; i <= n; i++) {
                        t = read<int>();
                        tree[log14(t)].insert(i, t);
                    }
                    int lastans = 0;
                    while (m--) {
                        if (read<int>() == 1) {
                            int l = read<int>(), r = read<int>(), x = read<int>();
                            l ^= lastans, r ^= lastans, x ^= lastans;
                            for (register int i = 0; i < 8; i++) tree[i].update(l, r, x), tree[i].findEmpty(1 << (2 * i));
                            for (vector<pii>::iterator i = empty.begin(); i != empty.end(); i++)
                                tree[log14(i->second)].insert(i->first, i->second);
                            empty.clear();
                        } else {
                            int l = read<int>(), r = read<int>();
                            l ^= lastans, r ^= lastans;
                            SegmentTree::AnsType answer;
                            for (register int i = 0; i < 8; i++) answer = answer + tree[i].getAns(l, r);
                            write(answer.sum), putch(' '), write(answer.minVal), putch(' '), write(answer.maxVal), putch('\n');
                            lastans = answer.sum & ((1 << 20) - 1);
                        }
                    }
                    return 0;
                }
                
                👍 3
                • @ 2022-3-20 7:52:09

                  #022 2022.3.20

                  标签:数据结构,线段树,树链剖分。

                  Statement

                  给定一棵 nn 个点的树,每个节点上均有一个二进制运算符(&|^)和一个在 [0, 2k1][0,~2^k-1] 之间的数值。

                  接下来给定 mm 个操作,每个操作分为两类:

                  • 修改某个结点上的运算符与数值。
                  • 给定 x, y, zx,~y,~z,你可以先任意指定一个值 val[0, z]val \in [0,~z],然后在树上沿 xxyy 之间的简单路径从 xxyy 移动,每次到达一个结点后将 valval 变为 val op[i] a[i]val~op[i]~a[i]op[i]op[i] 为该节点上运算符,a[i]a[i] 为该节点上数值。最大化到达 yy 结点时的 valval 值并输出。

                  n, m105, 0k64n,~m \le 10^5,~0 \le k \le 64

                  Solution

                  Solution

                  由于询问时询问的是树上两点间路径的信息,不难想到通过树链剖分将每条路径转化为 logn\log n 个区间。

                  由于每个结点上的运算符均为二进制位运算符,运算过程中不同二进制位之间互不影响。我们可以考虑对于每一个二进制位分开来考虑其运算结果,即对于每一个二进制位都求出其为 0/10/1 时经过路径后的结果,最后通过类似数位 DP 的计算方法即可求出 [0, z][0,~z] 区间内的初值可产生的最大运算结果。

                  而由于询问时两点间的路径是有向的,从 xlcax \to lca 的路径是向上的,从 lcaylca \to y 的路径是向下的。将树上移动的顺序对应到区间上移动的顺序,不难发现 xlcax \to lca 的路径对应的区间都是从右向左经过的,lcaylca \to y 的路径对应的区间都是从左向右经过的。因此我们需要对于每一个区间都求出每一个二进制位初始为 0/10/1 时从左向右或是从右向左经过该区间之后的值。

                  考虑如何维护,建立一棵线段树,每个线段树结点都记录 l0[i], l1[i], r0[i], r1[i]l0[i],~l1[i],~r0[i],~r1[i] 分别表示:

                  • 二进制第 ii 位为 00 时从左向右经过该区间后该位的值。
                  • 二进制第 ii 位为 11 时从左向右经过该区间后该位的值。
                  • 二进制第 ii 位为 00 时从右向左经过该区间后该位的值。
                  • 二进制第 ii 位为 11 时从右向左经过该区间后该位的值。

                  每次合并两个结点 a, ba,~b 的信息时令:

                  • ans.l0[i] = a.l0[i] && b.l1[i] || !a.l0[i] && b.l0[i]
                  • ans.l1[i] = a.l1[i] && b.l1[i] || !a.l1[i] && b.l0[i]
                  • ans.r0[i] = b.r0[i] && a.r1[i] || !b.r0[i] && a.r0[i]
                  • ans.r1[i] = b.r1[i] && a.r1[i] || !b.r1[i] && a.r0[i]

                  即枚举某一位在经过第一个区间后的值,将其以初值代入第二个区间得到结果。

                  此时对于每一个询问我们将路径拆为 logn\log n 个区间,每个区间对应 logn\log n 个线段树结点,每次合并结点需要花费 O(k)O(k) 的时间,因此此时的总时间复杂度为 O(m×k×log2n)O(m \times k \times \log ^2n),无法通过本题。

                  Optimization

                  我们仔细分析上面的时间复杂度,发现两个 logn\log n 在该算法中都难以去除,因此我们考虑优化掉 O(k)O(k) 的时间复杂度。容易发现 O(k)O(k) 的时间复杂度来自线段数结点合并。

                  仔细观察我们发现对于 kk 位分别进行逻辑运算是非常浪费的,我们考虑将四个大小为 kk 的数组压为四个大小为 2k2^k 的数字,将逻辑运算转变为二进制位运算即可。对应的四个转移变为:

                  • ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0)
                  • ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0)
                  • ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0)
                  • ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0)

                  因此合并结点信息的复杂度优化到 O(1)O(1),总复杂度达到 O(m×log2n)O(m \times \log ^2n),足以通过此题。

                  Code

                  View on GitHub

                  /**
                   * @author Macesuted (i@macesuted.moe)
                   * @copyright Copyright (c) 2021
                   * @brief 
                   *      My Solution: https://macesuted.moe/article/h1034
                   */
                  
                  #include <bits/stdc++.h>
                  using namespace std;
                  
                  namespace io {
                  #define SIZE (1 << 20)
                  char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
                  int f, qr;
                  inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
                  inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
                  inline void putch(char x) {
                      *oS++ = x;
                      if (oS == oT) flush();
                      return;
                  }
                  string getstr(void) {
                      string s = "";
                      char c = getch();
                      while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
                      while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
                      return s;
                  }
                  void putstr(string str, int begin = 0, int end = -1) {
                      if (end == -1) end = str.size();
                      for (register int i = begin; i < end; i++) putch(str[i]);
                      return;
                  }
                  template <typename T>
                  inline T read() {
                      register T x = 0;
                      for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                          if (c == '-') f = -1;
                      for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
                      return x * f;
                  }
                  template <typename T>
                  inline void write(const T& t) {
                      register T x = t;
                      if (!x) putch('0');
                      if (x < 0) putch('-'), x = -x;
                      while (x) qu[++qr] = x % 10 + '0', x /= 10;
                      while (qr) putch(qu[qr--]);
                      return;
                  }
                  struct Flusher_ {
                      ~Flusher_() { flush(); }
                  } io_flusher_;
                  }  // namespace io
                  using io::getch;
                  using io::getstr;
                  using io::putch;
                  using io::putstr;
                  using io::read;
                  using io::write;
                  
                  #define maxn 100005
                  
                  class SegmentTree {
                     public:
                      struct Node {
                          unsigned long long l0, l1, r0, r1;
                          Node(void) { l0 = 0, l1 = ~0, r0 = 0, r1 = ~0; }
                          Node operator+(const Node& b) const {
                              Node a = *this, ans;
                              ans.l0 = (a.l0 & b.l1) | (~a.l0 & b.l0);
                              ans.l1 = (a.l1 & b.l1) | (~a.l1 & b.l0);
                              ans.r0 = (b.r0 & a.r1) | (~b.r0 & a.r0);
                              ans.r1 = (b.r1 & a.r1) | (~b.r1 & a.r0);
                              return ans;
                          }
                      };
                      Node tree[maxn << 2];
                      int n;
                  
                      void update(int p, int l, int r, int qp, int opt, unsigned long long val) {
                          if (l == r) {
                              if (opt == 1)
                                  tree[p].l0 = tree[p].r0 = 0, tree[p].l1 = tree[p].r1 = val;
                              else if (opt == 2)
                                  tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~0;
                              else
                                  tree[p].l0 = tree[p].r0 = val, tree[p].l1 = tree[p].r1 = ~val;
                              return;
                          }
                          int mid = (l + r) >> 1;
                          qp <= mid ? update(p << 1, l, mid, qp, opt, val) : update(p << 1 | 1, mid + 1, r, qp, opt, val);
                          tree[p] = tree[p << 1] + tree[p << 1 | 1];
                          return;
                      }
                      Node merge(int p, int l, int r, int ql, int qr) {
                          if (ql <= l && r <= qr) return tree[p];
                          int mid = (l + r) >> 1;
                          Node answer;
                          if (ql <= mid) answer = answer + merge(p << 1, l, mid, ql, qr);
                          if (qr > mid) answer = answer + merge(p << 1 | 1, mid + 1, r, ql, qr);
                          return answer;
                      }
                      inline void resize(int tn) { return n = tn, void(); }
                      inline void update(int p, int opt, unsigned long long val) { return update(1, 1, n, p, opt, val); }
                      inline Node merge(int l, int r) { return merge(1, 1, n, l, r); }
                  };
                  
                  SegmentTree tree;
                  
                  int opt[maxn];
                  unsigned long long val[maxn];
                  
                  vector<vector<int> > graph;
                  
                  int dep[maxn], siz[maxn], son[maxn], top[maxn], fa[maxn], dfn[maxn];
                  
                  void dfs1(int p, int pre = 0) {
                      dep[p] = dep[pre] + 1, fa[p] = pre, siz[p] = 1;
                      for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
                          if (*i != pre) {
                              dfs1(*i, p);
                              if (!son[p] || siz[*i] > siz[son[p]]) son[p] = *i;
                              siz[p] += siz[*i];
                          }
                      return;
                  }
                  int tim = 0;
                  void dfs2(int p, int t) {
                      dfn[p] = ++tim, top[p] = t;
                      if (son[p]) dfs2(son[p], t);
                      for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++)
                          if (*i != fa[p] && *i != son[p]) dfs2(*i, *i);
                      return;
                  }
                  int lca(int x, int y) {
                      while (top[x] != top[y]) {
                          if (dep[top[x]] < dep[top[y]]) swap(x, y);
                          x = fa[top[x]];
                      }
                      return dep[x] < dep[y] ? x : y;
                  }
                  
                  int main() {
                      int n = read<int>(), m = read<int>(), k = read<int>();
                      graph.resize(n + 1);
                      for (register int i = 1; i <= n; i++) opt[i] = read<int>(), val[i] = read<unsigned long long>();
                      for (register int i = 1, from, to; i < n; i++) {
                          from = read<int>(), to = read<int>();
                          graph[from].push_back(to), graph[to].push_back(from);
                      }
                      dfs1(1), dfs2(1, 1);
                      tree.resize(n);
                      for (register int i = 1; i <= n; i++) tree.update(dfn[i], opt[i], val[i]);
                      while (m--)
                          if (read<int>() == 1) {
                              int x = read<int>(), y = read<int>(), t = lca(x, y);
                              unsigned long long z = read<unsigned long long>();
                              SegmentTree::Node record1, record2;
                              while (top[x] != top[t]) record1 = tree.merge(dfn[top[x]], dfn[x]) + record1, x = fa[top[x]];
                              record1 = tree.merge(dfn[t], dfn[x]) + record1;
                              while (top[y] != top[t]) record2 = tree.merge(dfn[top[y]], dfn[y]) + record2, y = fa[top[y]];
                              if (y != t) record2 = tree.merge(dfn[t] + 1, dfn[y]) + record2;
                              swap(record1.l0, record1.r0), swap(record1.l1, record1.r1);
                              SegmentTree::Node record = record1 + record2;
                              bool up = true;
                              unsigned long long answer = 0;
                              for (register int i = k - 1; ~i; i--) {
                                  unsigned long long l0 = (record.l0 >> i & 1), l1 = (record.l1 >> i & 1), t = (z >> i & 1);
                                  if (!up)
                                      answer |= max(l0, l1) << i;
                                  else if (t == 0)
                                      answer |= l0 << i;
                                  else if (l0 >= l1)
                                      answer |= l0 << i, up = false;
                                  else
                                      answer |= l1 << i;
                              }
                              cout << answer << endl;
                          } else {
                              int p = read<int>(), opt = read<int>();
                              unsigned long long val = read<unsigned long long>();
                              tree.update(dfn[p], opt, val);
                          }
                      return 0;
                  }
                  
                  👍 4
                  • @ 2022-3-19 7:02:33

                    #021 2022.3.19

                    标签:数据结构,珂朵莉树,CDQ分治。

                    Statement

                    维护一个长为 nn 的序列 aia_i,有 mm 次操作。

                    • 将区间 [l, r][l,~r] 的值修改为 xx
                    • 询问区间 [l, r][l,~r] 出现了多少种不同的数,也就是说同一个数出现多次只算一个。

                    1n, m105, 1ai1091 \le n,~m \le 10^5,~1 \le a_i \le 10^9

                    Solution

                    Solution

                    区间数不同颜色数量问题我们常用的解决方案是记 preipre_i 等于最大的 jj 满足 j<ij < iaj=aia_j = a_i,数区间内满足 prei<lpre_i < l 的数量即为区间内的颜色数量。

                    此题的难点在于区间修改操作,经分析不难发现当一个区间 [l, r][l,~r] 被修改为 xxi(l, r], pre[i]=i1\forall i \in (l,~r],~pre[i]=i-1,所以在每次操作后我们只需要:

                    • prelpre_l 修改为上一个 xx 区间的右端点。
                    • 将下一个 xx 区间的左端点的 prepre 改为 rr
                    • (l, r](l,~r] 区间内的所有 preipre_i 改为 i1i-1

                    考虑 3 操作,如果我们在每次修改时将所有 preii1pre_i \neq i-1 的位置找出并修改为 i1i-1,全局花在 3 操作上的修改次数为 O(n+m)O(n+m):初始时每个 preipre_i 可能都不等于 i1i-1,而后面的 mm 个操作中每个操作最多只会让两个 preipre_i 修改得不等于 i1i-1,所以全局出现过 preipre_i 不等于 i1i-1 情况的次数为 O(n+m)O(n+m),所以花在 3 操作上的修改次数也就为 O(n+m)O(n+m)

                    考虑如何快速找出 preii1pre_i \neq i-1 的位置。容易发现这样的位置一定是一个连续颜色段的开头。因此我们对原序列建一颗 ODT,每次修改 [l, r][l,~r] 时,1 操作和 2 操作直接单点修改,3 操作找到 ODT 上被 [l, r][l,~r] 包含的所有连续颜色段,将它们全部删除并把它们的左端点的 prepre 设为 i1i-1 即可。

                    我们可以使用树套树在线维护修改操作并 O(log2n)O(\log^2 n) 解决查询操作。

                    考虑使用复杂度不变但空间更小的做法。

                    我们现在是在使用树套树在线解决带修改二维数点问题,考虑再开一维表示数据修改的时间,问题就转变为静态三维数点问题,离线 CDQ 分治即可。

                    时间复杂度仍旧为 O(mlog2n)O(m \log^2 n),空间复杂度优化到 O(n+m)O(n+m)

                    Code

                    View on GitHub

                    /**
                     * @author Macesuted (macesuted@qq.com)
                     * @copyright Copyright (c) 2021
                     * @brief
                     *      My Solution: https://macesuted.moe/article/h1065
                     */
                    
                    #include <bits/stdc++.h>
                    using namespace std;
                    
                    namespace io {
                    #define SIZE (1 << 20)
                    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
                    int f, qr;
                    inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
                    inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
                    inline void putch(char x) {
                        *oS++ = x;
                        if (oS == oT) flush();
                        return;
                    }
                    string getstr(void) {
                        queue<char> que;
                        char c = getch();
                        while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
                        while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch();
                        string s;
                        s.resize(que.size());
                        for (register int i = 0; i < (int)s.size(); i++) s[i] = que.front(), que.pop();
                        return s;
                    }
                    void putstr(string str, int begin = 0, int end = -1) {
                        if (end == -1) end = str.size();
                        for (register int i = begin; i < end; i++) putch(str[i]);
                        return;
                    }
                    template <typename T>
                    inline T read() {
                        register T x = 0;
                        for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                            if (c == '-') f = -1;
                        for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
                        return x * f;
                    }
                    template <typename T>
                    inline void write(const T& t) {
                        register T x = t;
                        if (!x) putch('0');
                        if (x < 0) putch('-'), x = -x;
                        while (x) qu[++qr] = x % 10 + '0', x /= 10;
                        while (qr) putch(qu[qr--]);
                        return;
                    }
                    struct Flusher_ {
                        ~Flusher_() { flush(); }
                    } io_flusher_;
                    }  // namespace io
                    using io::getch;
                    using io::getstr;
                    using io::putch;
                    using io::putstr;
                    using io::read;
                    using io::write;
                    
                    #define maxn 100005
                    
                    typedef pair<int, int> pii;
                    
                    struct Node {
                        int tim, pos, pre, delta;
                        inline bool operator<(const Node& oth) const { return this->pre < oth.pre; }
                    };
                    struct Ask {
                        int id, tim, l, r;
                        inline bool operator<(const Ask& oth) const { return this->l < oth.l; }
                    };
                    
                    vector<Node> nodes;
                    vector<Ask> asks;
                    
                    map<int, set<pii> > record;
                    
                    int a[maxn], pre[maxn];
                    
                    class ODT {
                       private:
                        map<pii, int> color;
                    
                        void split(int l, int mid, int r) {
                            int col = color[(pii){l, mid}] = color[(pii){mid + 1, r}] = color[(pii){l, r}];
                            color.erase((pii){l, r});
                            record[col].erase((pii){l, r}), record[col].insert((pii){l, mid}), record[col].insert((pii){mid + 1, r});
                            return;
                        }
                        void erase(int tim, int l, int r) {
                            int col = color[(pii){l, r}];
                            color.erase((pii){l, r});
                            set<pii>::iterator i = ++record[col].find((pii){l, r});
                            if (i != record[col].end())
                                nodes.push_back((Node){tim, i->first, pre[i->first], -1}),
                                    nodes.push_back((Node){tim, i->first, pre[i->first] = pre[l], +1});
                            nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = l - 1, +1});
                            record[col].erase((pii){l, r});
                            return;
                        }
                    
                       public:
                        inline void build(int l, int r, int col) {
                            return color[(pii){l, r}] = col, record[col].insert((pii){l, r}), void();
                        }
                        void insert(int tim, int l, int r, int col) {
                            map<pii, int>::iterator t = --color.lower_bound((pii){l + 1, 0});
                            if (t->first.first != l) split(t->first.first, l - 1, t->first.second);
                            t = --color.lower_bound((pii){r + 1, 0});
                            if (t->first.second != r) split(t->first.first, r, t->first.second);
                            while (true) {
                                map<pii, int>::iterator i = color.lower_bound((pii){l, 0});
                                if (i == color.end() || i->first.second > r) break;
                                erase(tim, i->first.first, i->first.second);
                            }
                            record[col].insert((pii){l, r});
                            set<pii>::iterator i = record[col].find((pii){l, r}), il = i, ir = i;
                            int p = 0;
                            if (il != record[col].begin()) p = (--il)->second;
                            nodes.push_back((Node){tim, l, pre[l], -1}), nodes.push_back((Node){tim, l, pre[l] = p, +1});
                            if (++ir != record[col].end())
                                nodes.push_back((Node){tim, ir->first, pre[ir->first], -1}),
                                    nodes.push_back((Node){tim, ir->first, pre[ir->first] = r, +1});
                            color[(pii){l, r}] = col;
                            // t = color.find((pii){l, r});
                            // if (t != color.begin() && (--t)->second == col) {
                            //     int nl = t->first.first;
                            //     record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r});
                            //     color.erase(t), color.erase((pii){l, r});
                            //     record[col].insert((pii){l = nl, r});
                            //     color[(pii){l, r}] = col;
                            // }
                            // t = ++color.find((pii){l, r});
                            // if (t != color.end() && t->second == col) {
                            //     int nr = t->first.second;
                            //     record[col].erase((pii){t->first.first, t->first.second}), record[col].erase((pii){l, r});
                            //     color.erase(t), color.erase((pii){l, r});
                            //     record[col].insert((pii){l, r = nr});
                            //     color[(pii){l, r}] = col;
                            // }
                            return;
                        }
                    };
                    class BIT {
                       private:
                        int tree[maxn];
                    
                       public:
                        void add(int p, int val) {
                            for (register int i = p; i < maxn; i += i & -i) tree[i] += val;
                            return;
                        }
                        int sum(int p) {
                            int sum = 0;
                            for (register int i = p; i; i -= i & -i) sum += tree[i];
                            return sum;
                        }
                    };
                    
                    ODT tree;
                    BIT bit;
                    
                    int answer[maxn];
                    
                    void CDQ(int nl, int nr, int ql, int qr, int tl, int tr) {
                        if (nl > nr || ql > qr) return;
                        int tmid = (tl + tr) >> 1, nmid = nl - 1, qmid = ql - 1;
                        while (nmid < nr && nodes[nmid + 1].tim <= tmid) nmid++;
                        while (qmid < qr && asks[qmid + 1].tim <= tmid) qmid++;
                        CDQ(nl, nmid, ql, qmid, tl, tmid), CDQ(nmid + 1, nr, qmid + 1, qr, tmid + 1, tr);
                        if (nl > nmid || qmid + 1 > qr) return;
                        sort(nodes.begin() + nl, nodes.begin() + nmid + 1), sort(asks.begin() + qmid + 1, asks.begin() + qr + 1);
                        int j = nl;
                        for (register int i = qmid + 1; i <= qr; i++) {
                            while (j <= nmid && asks[i].l > nodes[j].pre) bit.add(nodes[j].pos, nodes[j].delta), j++;
                            answer[asks[i].id] += bit.sum(asks[i].r) - bit.sum(asks[i].l - 1);
                        }
                        for (register int i = nl; i < j; i++) bit.add(nodes[i].pos, -nodes[i].delta);
                        return;
                    }
                    
                    int main() {
                        int n = read<int>(), m = read<int>();
                        for (register int i = 1; i <= n; i++) a[i] = read<int>();
                        for (register int i = 1, j; i <= n; i = j + 1) {
                            j = i;
                            while (j < n && a[j + 1] == a[i]) j++;
                            tree.build(i, j, a[i]);
                            set<pii>::iterator t = record[a[i]].find((pii){i, j});
                            int p = 0;
                            if (t != record[a[i]].begin()) p = (--t)->second;
                            pre[i] = p;
                            for (register int k = i + 1; k <= j; k++) pre[k] = k - 1;
                        }
                        for (register int i = 1; i <= n; i++) nodes.push_back((Node){0, i, pre[i], +1});
                        for (register int i = 1; i <= m; i++)
                            if (read<int>() == 1) {
                                int l = read<int>(), r = read<int>(), col = read<int>();
                                tree.insert(i, l, r, col);
                            } else {
                                int l = read<int>(), r = read<int>();
                                asks.push_back((Ask){(int)asks.size(), i, l, r});
                            }
                        // for (vector<Node>::iterator i = nodes.begin(); i != nodes.end(); i++)
                        //     cerr << i->tim << ' ' << i->pos << ' ' << i->pre << ' ' << i->delta << endl;
                        CDQ(0, (int)nodes.size() - 1, 0, (int)asks.size() - 1, 0, m);
                        for (register int i = 0; i < (int)asks.size(); i++) write(answer[i]), putch('\n');
                        return 0;
                    }
                    
                    👍 6
                    ❤️ 1
                    • @ 2022-3-18 6:50:57

                      #020 2022.3.18

                      标签:数据结构,线段树。

                      []

                      Statement

                      现在有一个数字序列 a1, a2,, an{a_1,~a_2,\dots,~a_n} 和一个运算符序列 p1, p2,, an1{p_1,~p_2,\dots,~a_{n-1}}

                      定义 w(l, r)w(l,~r) 表示 al pl al+1 pl+1  ar1 pr1 ara_l~p_l~a_{l+1}~p_{l+1}~\dots~a_{r-1}~p_{r-1}~a_r109+710^9+7 取模后的结果。

                      现有 mm 个操作:

                      • alara_l \sim a_r 修改为 xx
                      • plprp_l \sim p_r 修改为 xx
                      • w(l, r)w(l,~r) 的值。

                      1n, m105, 1ai<232, pi{+, ×}1 \le n,~m \le 10^5,~1 \le a_i < 2^{32},~p_i \in \{+,~\times\}

                      Solution

                      Solution

                      考虑我们如何暴力计算 w(l, r)w(l,~r),我们会先将 [l, r][l,~r] 区间切分为若干满足每段内所有符号均为 ×\times 的极长段。如 1+3×5×7+9×111+3\times5\times7+9\times11 将被分割为 [1], [3, 5, 7], [9, 11][1],~[3,~5,~7],~[9,~11]。分割完后我们对每个极长段求出段内乘积,再将所有段的结果加起来即为我们所求的 w(l, r)w(l,~r)

                      先考虑没有修改操作只有查询操作的情况,对于每一个查询区间我们需要知道区间内所有极长段的乘积之和,容易想到使用线段树维护。线段树上每一个结点维护对应区间的最左端极长段乘积,最右端极长段乘积和其他极长段乘积之和。合并两个区间信息时判断左结点的最右端极长段与右结点的最左端极长段是否能够连接即可。

                      考虑加入 1 操作,对 aa 序列的区间修改操作在线段树上体现为对 O(logn)O(\log n) 个区间的整段修改操作。我们发现对于一个线段树结点,当他对应的区间被整段修改后其所有极长段左右端点均没有发生变化,而所有极长段的段内乘积会发生改变。我们考虑对于每个节点维护一个桶维护其所有非最左端也非最右端的极长段长度,在将该节点整段修改为 xx 时只需要将答案更新为 ixi×midLen[i]\sum_{i} x^{i} \times midLen[i] 即可。同时我们也需要记录最左端极长段长度和最右端极长段长度,这样在合并线段树结点信息时即可将左结点的最右端极长段与右结点的最左端极长段合并后构成的新极长段长度加入桶中。

                      考虑加入 2 操作,同样我们也可以将对 pp 序列的区间修改在线段树上体现为对 O(logn)O(\log n) 个区间的整段修改操作。由于修改为 ++ 和修改为 ×\times 的情况不同,我们分开讨论:

                      • 整段修改为 ++: 修改后该区间内会产生 lenlen 个长为 11 的极长段,ansans 将变为 i=l+1r1ai\sum_{i=l+1}^{r-1} a_i。为此对每个节点我们维护整段元素和以快速维护此修改操作。
                      • 整段修改为 ×\times: 修改后该区间内会产生 11 个长为 lenlen 的极长段,此时该极长段的乘积为 i=lrai\prod_{i=l}^{r} a_i。为此对每个节点我们维护整段元素乘积以快速维护此修改操作。

                      在线段树上维护上述所有信息即可,此时时间复杂度为 O(n×logn+m×n×logn)O(n \times \log n + m \times n \times \log n),空间复杂度为 O(n×logn)O(n \times \log n)。时间复杂度与空间复杂度均无法通过此题。

                      优化 1

                      对于每个线段树结点,其区间内所有极长段的长度之和为 lenlen,因此最多只会存在 len\sqrt {len} 种不同的极长段长度,将相同长度的极长段的信息在一起存储,使用大小为 len\sqrt {len}vector 存储即可。

                      此时时间复杂度 O(n+m×n×logn)O(n + m \times \sqrt n \times \log n),空间复杂度 O(n)O(n)。时间复杂度仍无法通过此题。

                      优化 2

                      在区间修改元素值时我们对 O(n)O(\sqrt n) 个长度都 O(logn)O(\log n) 求该长度对应区间修改后的乘积。考虑存储连续段长度时按连续段长度升序存储,需要对第 ii 个长度求值时从第 i1i-1 个长度对应的答案转移过来。因为 O(ilog(aiai1))=O(logan)=O(len)O(\sum_{i} \log (a_i - a_{i-1})) = O(\log a_n) = O(\sqrt {len}),所以花在对 O(n)O(\sqrt n) 个长度求值的时间复杂度转为 O(n)O(\sqrt n)

                      此时时间复杂度 O(n+m×n)O(n + m \times \sqrt n),空间复杂度 O(n)O(n),可以通过此题。

                      也可以考虑以恰当块长对线段树底层进行分块以继续减少空间占用。

                      Code

                      View on GitHub

                      /**
                       * @author Macesuted (i@macesuted.moe)
                       * @copyright Copyright (c) 2021
                       * @brief
                       *      My solution: https://macesuted.moe/article/lg5608
                       */
                      
                      #include <bits/stdc++.h>
                      using namespace std;
                      
                      namespace io {
                      #define SIZE (1 << 20)
                      char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
                      int f, qr;
                      inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
                      inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
                      inline void putch(char x) {
                          *oS++ = x;
                          if (oS == oT) flush();
                          return;
                      }
                      string getstr(void) {
                          string s = "";
                          char c = getch();
                          while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
                          while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
                          return s;
                      }
                      void putstr(string str, int begin = 0, int end = -1) {
                          if (end == -1) end = str.size();
                          for (register int i = begin; i < end; i++) putch(str[i]);
                          return;
                      }
                      template <typename T>
                      inline T read() {
                          register T x = 0;
                          for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                              if (c == '-') f = -1;
                          for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
                          return x * f;
                      }
                      template <typename T>
                      inline void write(const T& t) {
                          register T x = t;
                          if (!x) putch('0');
                          if (x < 0) putch('-'), x = -x;
                          while (x) qu[++qr] = x % 10 + '0', x /= 10;
                          while (qr) putch(qu[qr--]);
                          return;
                      }
                      struct Flusher_ {
                          ~Flusher_() { flush(); }
                      } io_flusher_;
                      }  // namespace io
                      using io::getch;
                      using io::getstr;
                      using io::putch;
                      using io::putstr;
                      using io::read;
                      using io::write;
                      
                      #define maxn 100005
                      #define sqrtn 320
                      #define mod 1000000007
                      #define leafLen 50
                      
                      typedef pair<int, int> pii;
                      
                      long long Pow(long long a, long long x) {
                          long long ans = 1;
                          while (x) {
                              if (x & 1) ans = ans * a % mod;
                              a = a * a % mod;
                              x >>= 1;
                          }
                          return ans;
                      }
                      
                      inline int Mod(int x) { return x >= mod ? x - mod : x; }
                      
                      pii cache[sqrtn];
                      
                      class SegmentTree {
                         private:
                          struct Node {
                              bool op, hasLazyOp, lazyOp, hasLazyNum;
                              long long allMul, lMul, rMul;
                              int allPlus, ans, lazyNum;
                              int lNum, rNum, lLen, rLen;
                              pii midLen[sqrtn];
                              int tail;
                              int len, sqrtLen;
                              Node *l, *r;
                              Node(void) { hasLazyOp = hasLazyNum = false, l = r = NULL, tail = 0; }
                              void add(int val, int cnt = 1) {
                                  if (val == 0) return;
                                  for (register int i = 1; i <= tail; i++)
                                      if (midLen[i].first == val) return midLen[i].second += cnt, void();
                                  int p = tail++;
                                  while (p > 0 && midLen[p].first > val) swap(midLen[p], midLen[p + 1]), p--;
                                  midLen[p + 1] = (pii){val, cnt};
                                  return;
                              }
                              Node operator+(const Node& oth) const {
                                  Node a = *this, b = oth;
                                  a.hasLazyOp = a.hasLazyNum = false;
                                  a.allMul = a.allMul * b.allMul % mod;
                                  a.allPlus = Mod(a.allPlus + b.allPlus);
                                  a.rNum = b.rNum;
                                  a.sqrtLen = sqrt(a.len += b.len);
                                  int ctail = a.tail;
                                  for (register int i = 1; i <= a.tail; i++) cache[i] = a.midLen[i];
                                  int pb = 1, pc = 1;
                                  a.tail = 0;
                                  while (pb <= b.tail && pc <= ctail)
                                      if (b.midLen[pb].first == cache[pc].first)
                                          a.midLen[++a.tail] = (pii){b.midLen[pb].first, b.midLen[pb].second + cache[pc].second}, pb++, pc++;
                                      else if (b.midLen[pb].first < cache[pc].first)
                                          a.midLen[++a.tail] = b.midLen[pb], pb++;
                                      else
                                          a.midLen[++a.tail] = cache[pc], pc++;
                                  while (pb <= b.tail) a.midLen[++a.tail] = b.midLen[pb], pb++;
                                  while (pc <= ctail) a.midLen[++a.tail] = cache[pc], pc++;
                                  if (!a.op) {
                                      if (!a.lLen) swap(a.lLen, a.rLen), swap(a.lMul, a.rMul);
                                      if (!b.rLen) swap(b.lLen, b.rLen), swap(b.lMul, b.rMul);
                                      a.ans = Mod(Mod(a.ans + b.ans) + Mod(a.rMul + b.lMul));
                                      a.add(a.rLen), a.add(b.lLen);
                                      a.rLen = b.rLen, a.rMul = b.rMul;
                                  } else {
                                      if (!a.rLen) swap(a.lLen, a.rLen), swap(a.lMul, a.rMul);
                                      if (!b.lLen) swap(b.lLen, b.rLen), swap(b.lMul, b.rMul);
                                      int nLen = a.rLen + b.lLen, nMul = a.rMul * b.lMul % mod;
                                      a.ans = Mod(a.ans + b.ans);
                                      a.rLen = b.rLen, a.rMul = b.rMul;
                                      if (!a.lLen)
                                          a.lLen = nLen, a.lMul = nMul;
                                      else if (!a.rLen)
                                          a.rLen = nLen, a.rMul = nMul;
                                      else
                                          a.ans = Mod(a.ans + nMul), a.add(nLen);
                                  }
                                  a.op = b.op;
                                  return a;
                              }
                              int getAns(void) {
                                  int ans = this->ans;
                                  if (lLen) ans = Mod(ans + lMul);
                                  if (rLen) ans = Mod(ans + rMul);
                                  return ans;
                              }
                          };
                      
                          Node* root;
                      
                          int a[maxn], op[maxn];
                      
                          int n;
                      
                          Node merge(Node* l, Node* r) {
                              Node ans = *l + *r;
                              ans.l = l, ans.r = r;
                              return ans;
                          }
                          Node reCalc(int l, int r) {
                              Node p;
                              p.op = op[r], p.ans = 0;
                              p.tail = 0;
                              p.lNum = a[l], p.rNum = a[r];
                              p.lLen = 1, p.lMul = a[l], p.rLen = 0, p.rMul = 0;
                              p.sqrtLen = sqrt(p.len = r - l + 1);
                              while (l + p.lLen <= r && op[l + p.lLen - 1]) p.lMul = p.lMul * a[l + p.lLen] % mod, p.lLen++;
                              if (l + p.lLen - 1 < r) {
                                  p.rLen = 1, p.rMul = a[r];
                                  while (op[r - p.rLen]) p.rMul = p.rMul * a[r - p.rLen] % mod, p.rLen++;
                                  int tl = l + p.lLen, tr = r - p.rLen;
                                  if (tl <= tr) {
                                      long long last = a[tl];
                                      int lastPos = tl;
                                      for (register int i = tl; i < tr; i++)
                                          if (op[i])
                                              last = last * a[i + 1] % mod;
                                          else
                                              p.ans = Mod(p.ans + last), p.add(i - lastPos + 1), last = a[lastPos = i + 1];
                                      p.add(tr - lastPos + 1), p.ans = Mod(p.ans + last);
                                  }
                              }
                              p.allMul = 1, p.allPlus = 0;
                              for (register int i = l; i <= r; i++) p.allMul = p.allMul * a[i] % mod, p.allPlus = Mod(p.allPlus + a[i]);
                              return p;
                          }
                          void modifyNum(Node* p, int l, int r, int num) {
                              if (r - l + 1 < leafLen) {
                                  for (register int i = l; i <= r; i++) a[i] = num;
                                  *p = reCalc(l, r);
                                  return;
                              }
                              p->allMul = Pow(num, r - l + 1), p->allPlus = 1LL * (r - l + 1) * num % mod, p->ans = 0;
                              long long lastPow = 1;
                              int lastPos = 0;
                              for (register int i = 1; i <= p->tail; i++)
                                  lastPow = lastPow * Pow(num, p->midLen[i].first - lastPos) % mod, lastPos = p->midLen[i].first,
                                  p->ans = (p->ans + lastPow * p->midLen[i].second) % mod;
                              p->lNum = p->rNum = num;
                              if (p->lLen) p->lMul = Pow(num, p->lLen);
                              if (p->rLen) p->rMul = Pow(num, p->rLen);
                              p->hasLazyNum = true, p->lazyNum = num;
                              return;
                          }
                          inline void modifyOp(Node* p, int l, int r, bool _op) {
                              if (r - l + 1 < leafLen) {
                                  for (register int i = l; i <= r; i++) op[i] = _op;
                                  *p = reCalc(l, r);
                                  return;
                              }
                              p->op = _op;
                              if (!_op) {
                                  p->ans = Mod(Mod(p->allPlus + mod - p->lNum) + mod - p->rNum);
                                  p->lLen = 1, p->lMul = p->lNum;
                                  p->rLen = 1, p->rMul = p->rNum;
                                  p->tail = 0, p->add(1, r - l - 1);
                              } else {
                                  p->ans = 0;
                                  p->lLen = r - l + 1, p->lMul = p->allMul;
                                  p->rLen = 0, p->rMul = 0;
                                  p->tail = 0;
                              }
                              p->hasLazyOp = true, p->lazyOp = _op;
                              return;
                          }
                          inline void pushDown(Node* p, int l, int r) {
                              int mid = (l + r) >> 1;
                              if (p->hasLazyOp) {
                                  p->hasLazyOp = false;
                                  modifyOp(p->l, l, mid, p->lazyOp), modifyOp(p->r, mid + 1, r, p->lazyOp);
                              }
                              if (p->hasLazyNum) {
                                  p->hasLazyNum = false;
                                  modifyNum(p->l, l, mid, p->lazyNum), modifyNum(p->r, mid + 1, r, p->lazyNum);
                              }
                              return;
                          }
                          void build(Node*& p, int l, int r, int _a[], bool _op[]) {
                              if (p == NULL) p = new Node();
                              if (r - l + 1 < leafLen) {
                                  for (register int i = l; i <= r; i++) a[i] = _a[i], op[i] = _op[i];
                                  p->sqrtLen = sqrt(p->len = r - l + 1);
                                  *p = reCalc(l, r);
                                  return;
                              }
                              int mid = (l + r) >> 1;
                              build(p->l, l, mid, _a, _op), build(p->r, mid + 1, r, _a, _op);
                              *p = merge(p->l, p->r);
                              return;
                          }
                          void updateNum(Node* p, int l, int r, int ql, int qr, int val) {
                              if (ql <= l && r <= qr) return modifyNum(p, l, r, val);
                              if (r - l + 1 < leafLen) {
                                  for (register int i = max(l, ql); i <= min(r, qr); i++) a[i] = val;
                                  *p = reCalc(l, r);
                                  return;
                              }
                              pushDown(p, l, r);
                              int mid = (l + r) >> 1;
                              if (ql <= mid) updateNum(p->l, l, mid, ql, qr, val);
                              if (qr > mid) updateNum(p->r, mid + 1, r, ql, qr, val);
                              *p = merge(p->l, p->r);
                              return;
                          }
                          void updateOp(Node* p, int l, int r, int ql, int qr, bool _op) {
                              if (ql <= l && r <= qr) return modifyOp(p, l, r, _op);
                              if (r - l + 1 < leafLen) {
                                  for (register int i = max(l, ql); i <= min(r, qr); i++) op[i] = _op;
                                  *p = reCalc(l, r);
                                  return;
                              }
                              pushDown(p, l, r);
                              int mid = (l + r) >> 1;
                              if (ql <= mid) updateOp(p->l, l, mid, ql, qr, _op);
                              if (qr > mid) updateOp(p->r, mid + 1, r, ql, qr, _op);
                              *p = merge(p->l, p->r);
                              return;
                          }
                          Node getAns(Node* p, int l, int r, int ql, int qr) {
                              if (ql <= l && r <= qr) return *p;
                              if (r - l + 1 < leafLen) return reCalc(max(l, ql), min(r, qr));
                              int mid = (l + r) >> 1;
                              pushDown(p, l, r);
                              if (qr <= mid) return getAns(p->l, l, mid, ql, qr);
                              if (ql > mid) return getAns(p->r, mid + 1, r, ql, qr);
                              return getAns(p->l, l, mid, ql, qr) + getAns(p->r, mid + 1, r, ql, qr);
                          }
                      
                         public:
                          SegmentTree(void) { root = NULL; }
                          inline void resize(int _n) { return n = _n, void(); }
                          inline void build(int a[], bool op[]) { return build(root, 1, n, a, op); }
                          inline void updateNum(int l, int r, int val) { return updateNum(root, 1, n, l, r, val); }
                          inline void updateOp(int l, int r, bool op) { return updateOp(root, 1, n, l, r, op); }
                          inline int getAns(int l, int r) { return getAns(root, 1, n, l, r).getAns(); }
                      };
                      
                      SegmentTree tree;
                      
                      int a[maxn];
                      bool op[maxn];
                      
                      int main() {
                          int n = read<int>(), m = read<int>();
                          for (register int i = 1; i <= n; i++) a[i] = read<long long>() % mod;
                          for (register int i = 1; i < n; i++) op[i] = read<int>();
                          tree.resize(n), tree.build(a, op);
                          while (m--) {
                              int opt = read<int>();
                              if (opt == 1) {
                                  int l = read<int>(), r = read<int>();
                                  tree.updateNum(l, r, read<long long>() % mod);
                              } else if (opt == 2) {
                                  int l = read<int>(), r = read<int>();
                                  tree.updateOp(l, r, read<int>());
                              } else {
                                  int l = read<int>(), r = read<int>();
                                  write(tree.getAns(l, r)), putch('\n');
                              }
                          }
                          return 0;
                      }
                      
                      👍 3
                      • @ 2022-3-17 6:46:57

                        #019 2022.3.17

                        标签:构造,高斯消元。

                        Statement

                        给出 50005000 个可以让你使用的变量,其中前两个变量分别为 x, yx,~y。你并不知道 x, yx,~y 具体值,请你利用下面两中运算令某一变量值为 x×yx \times y:

                        1. + a b c:将变量 aa 与变量 bb 相加,结果输出到变量 cc
                        2. ^ a b:将变量 aadd 次方输出到变量 bbdd 为题目初始时给出的定值。

                        所有运算均在模 pp 意义下进行。

                        2d10, p is prime2 \le d \le 10,~p~\text{is prime}

                        Solution

                        Solution

                        考虑 d=2d = 2 时怎么做。

                        容易发现答案即为 (a+b)2a2b22\dfrac {(a + b)^2 - a^2 - b^2} 2,需要支持减法和除以二操作。容易发现 aba - b 即为 a+b×(p1)a + b \times (p - 1)a2\frac a 2a×2p2a \times 2^{p - 2}。即我们只需要额外实现乘法,使用龟速乘实现即可。即要求 a×ca \times ccc 为常数),仅通过加法即可计算出 a, 2×a, 4×a, 8×a,a,~2 \times a,~4 \times a,~8 \times a,\dots,最终将 cc 二进制拆分后将对应位置上的值加起来即可。

                        考虑 d2d \neq 2 的情况,我们尝试构造 a0, a1,,ada_0,~a_1,\dots,a_d 使满足 x2=i=0dai×(x+i)dx^2 = \sum_{i = 0}^{d} a_i \times (x + i)^d。其为 i=0dxt×j=0daj×jdj×(dj)\sum_{i = 0}^{d} x^t \times \sum_{j = 0}^{d} a_j \times j^{d - j} \times {d \choose j},我们想要使得 x2x^2 次项系数为 11,其余均为 00,其构成 d+1d + 1 个线性方程,使用高斯消元求解出一组合法的 aa 即可。

                        因此我们可以通过上述方法完成平方操作,再使用 d=2d = 2 时的做法即可求出最终答案。龟速乘操作复杂度 O(logn)O(\log n),平方操作复杂度 O(dlogn)O(d \log n),最终复杂度 O(dlogn)O(d \log n)

                        Code

                        View on GitHub

                        /**
                         * @file 1060H.cpp
                         * @author Macesuted (i@macesuted.moe)
                         * @date 2022-03-09
                         *
                         * @copyright Copyright (c) 2022
                         *
                         */
                        
                        #include <bits/stdc++.h>
                        using namespace std;
                        
                        namespace io {
                        const int SIZE = 1 << 20;
                        char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
                        char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
                        void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
                        void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
                        char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
                        char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
                        void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
                        template <typename T>
                        T read(void) {
                            T x = 0, f = +1;
                            char c = getch();
                            while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
                            while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
                            return x * f;
                        }
                        template <typename T>
                        void write(T x) {
                            if (!x) putch('0');
                            if (x < 0) putch('-'), x = -x;
                            int top = 0;
                            while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
                            while (top) putch(stack[--top]);
                            return;
                        }
                        string getstr(const string& suf = "") {
                            string s = suf;
                            while (isspace(buftop())) getch();
                            while (Il != Ir) {
                                char* p = Il;
                                while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
                                s.append(p, Il);
                                if (Il < Ir) break;
                                fill();
                            }
                            return s;
                        }
                        void putstr(string str, int begin = 0, int end = -1) {
                            if (end == -1) end = str.size();
                            for (int i = begin; i < end; i++) putch(str[i]);
                            return;
                        }
                        struct Flusher_ {
                            ~Flusher_() { flush(); }
                        } io_flusher_;
                        }  // namespace io
                        using io::getch;
                        using io::getstr;
                        using io::putch;
                        using io::putstr;
                        using io::read;
                        using io::write;
                        
                        bool mem1;
                        
                        int a[12][12], c[12], binom[12][12], d, mod;
                        
                        long long Pow(long long a, long long x) {
                            long long ans = 1;
                            while (x) {
                                if (x & 1) ans = ans * a % mod;
                                a = a * a % mod, x >>= 1;
                            }
                            return ans;
                        }
                        
                        void opPlus(int x, int y, int to) { return putstr("+ "), write(x), putch(' '), write(y), putch(' '), write(to), putch('\n'); }
                        void opPow(int x, int to) { return putstr("^ "), write(x), putch(' '), write(to), putch('\n'); }
                        
                        int empt = 50;
                        int multi(int x, int v) {
                            vector<int> cache;
                            if (v & 1) cache.push_back(x), v--;
                            for (int i = 1, last = x; v; i++) {
                                opPlus(last, last, empt);
                                if (v >> i & 1) cache.push_back(empt), v -= 1 << i;
                                last = empt++;
                            }
                            if (cache.size() == 1) return cache.front();
                            int to = empt++;
                            opPlus(cache[0], cache[1], to);
                            for (int i = 2; i < (int)cache.size(); i++) opPlus(to, cache[i], to);
                            return to;
                        }
                        int pow2(int p) {
                            vector<int> cache;
                            for (int i = 0; i <= d; i++, opPlus(p, 5000, p)) {
                                int x = empt++;
                                opPow(p, x);
                                if (c[i]) cache.push_back(multi(x, c[i]));
                            }
                            if (cache.size() == 1) return cache.front();
                            int to = empt++;
                            opPlus(cache[0], cache[1], to);
                            for (int i = 2; i < (int)cache.size(); i++) opPlus(to, cache[i], to);
                            return to;
                        }
                        
                        void solve(void) {
                            d = read<int>(), mod = read<int>();
                            for (int i = 0; i <= d; i++) {
                                binom[i][0] = binom[i][i] = 1;
                                for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
                            }
                            for (int i = 0; i <= d; i++) {
                                for (int j = 0; j <= d; j++) a[i][j] = Pow(j, d - i) * binom[d][i] % mod;
                                a[i][d + 1] = (i == 2);
                            }
                            for (int i = 0; i <= d; i++) {
                                int p = i;
                                for (int j = i + 1; j <= d; j++)
                                    if (a[j][i] > a[p][i]) p = j;
                                for (int j = 0; j <= d + 1; j++) swap(a[i][j], a[p][j]);
                                long long inv = Pow(a[i][i], mod - 2);
                                for (int j = 0; j <= d + 1; j++) a[i][j] = a[i][j] * inv % mod;
                                for (int j = 0; j <= d; j++) {
                                    if (i == j) continue;
                                    long long x = a[j][i];
                                    for (int k = 0; k <= d + 1; k++) a[j][k] = (a[j][k] + mod - x * a[i][k] % mod) % mod;
                                }
                            }
                            for (int i = 0; i <= d; i++) c[i] = a[i][d + 1];
                            opPlus(1, 2, 3);
                            int p1 = multi(pow2(1), mod - 1), p2 = multi(pow2(2), mod - 1), p3 = pow2(3);
                            opPlus(p3, p1, p3), opPlus(p3, p2, p3);
                            int p = multi(p3, Pow(2, mod - 2));
                            putstr("f "), write(p), putch('\n');
                            return;
                        }
                        
                        bool mem2;
                        
                        int main() {
                        #ifdef MACESUTED
                            cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
                        #endif
                        
                            int _ = 1;
                            while (_--) solve();
                        
                        #ifdef MACESUTED
                            cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
                        #endif
                            return 0;
                        }
                        
                        • @ 2022-3-16 6:47:53

                          #018 2022.3.16

                          标签:数据结构,线段树,线段树分治。

                          Statement

                          有一个 n×nn \times n 的矩阵 aa,初始全是 00,有 mm 次修改操作和 qq 次查询操作,先进行所有修改操作,然后进行所有查询操作。

                          一次修改操作会给出 l1, l2, r1, r2, xl_1,~l_2,~r_1,~r_2,~x,代表把所有满足 l1ir1l_1 \le i \le r_1l2jr2l_2 \le j \le r_2ai,ja_{i,j} 元素加上一个值 xx

                          一次查询操作会给出 l1, l2, r1, r2l_1,~l_2,~r_1,~r_2,代表查询所有满足 l1ir1l_1 \le i \le r_1l2jr2l_2 \le j \le r_2ai,ja_{i,j} 元素的最大值。

                          1n, m5×104, 1q5×1051 \le n,~m \le 5 \times 10^4,~1 \le q \le 5 \times 10^5

                          Solution

                          Solution

                          由于询问数量远高于修改数量,考虑询问复杂度较低的算法。

                          考虑在 XX 轴上分治,对于分治区间 [l, r][l,~r] 我们求出所有 l1mid=l+r2r1l_1 \le mid = \lfloor \frac {l + r} 2 \rfloor \le r_1 的询问的答案。可以从 midmid 开始向左做一次扫描线,维护区间加减的同时维护区间历史最大值即可得到 maxl1imid, l2jr2ai, j\max_{l_1 \le i \le mid,~l_2 \le j \le r_2} a_{i,~j} 的值。同理再从 midmid 开始向右做一次扫描线,将 [l1, mid][l_1,~mid][mid, r1][mid,~r_1] 的答案取较大值即可得到原询问的答案。

                          为保持分治结构每层增减修改操作的数量保持在 O(n)O(n) 级别,考虑按该分治结构建立线段树,对于每个修改操作,按线段树插入的方法插入到线段树中。插入操作最终到达的 logn\log n 个被 [l1, r1][l_1,~r_1] 包含的结点采用类似标记永久化的方法,线段树分治进入该结点子树时加入该修改操作贡献,离开该结点子树时减去该修改操作贡献。对于线段树上其他 O(logn)O(\log n) 个存在一部分被修改操作包含的结点,在其内分治执行扫描线过程时最多会进行 22 次区间修改操作,因此全局花在维护修改操作贡献上的时间复杂度为 O(mlog2n)O(m \log^2 n)

                          总时间复杂度 O(mlog2n+qlogn)O(m \log^2 n + q \log n)

                          Code

                          View on GitHub

                          /**
                           * @file 6109.cpp
                           * @author Macesuted (i@macesuted.moe)
                           * @date 2022-03-11
                           *
                           * @copyright Copyright (c) 2022
                           *
                           */
                          
                          #include <bits/stdc++.h>
                          using namespace std;
                          
                          namespace IO {
                          const int SIZE = 1 << 20;
                          char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1, stack[32];
                          char isspace(char c) { return c == ' ' || c == 't' || c == 'n' || c == 'v' || c == 'f' || c == 'r'; }
                          void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
                          void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
                          char buftop(void) { return Ir == Il ? fill(), *Il : *Il; }
                          char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
                          void putch(char x) { return *Ol++ = x, Ol == Or ? flush() : void(); }
                          template <typename T>
                          T read(void) {
                              T x = 0, f = +1;
                              char c = getch();
                              while (c < '0' || c > '9') c == '-' ? void(f = -f) : void(), c = getch();
                              while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
                              return x * f;
                          }
                          template <typename T>
                          void write(T x) {
                              if (!x) putch('0');
                              if (x < 0) putch('-'), x = -x;
                              int top = 0;
                              while (x) stack[top++] = (x % 10) ^ 48, x /= 10;
                              while (top) putch(stack[--top]);
                              return;
                          }
                          string getstr(const string& suf = "") {
                              string s = suf;
                              while (isspace(buftop())) getch();
                              while (Il != Ir) {
                                  char* p = Il;
                                  while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
                                  s.append(p, Il);
                                  if (Il < Ir) break;
                                  fill();
                              }
                              return s;
                          }
                          void putstr(string str, int begin = 0, int end = -1) {
                              if (end == -1) end = str.size();
                              for (int i = begin; i < end; i++) putch(str[i]);
                              return;
                          }
                          struct Flusher_ {
                              ~Flusher_() { flush(); }
                          } io_flusher_;
                          }  // namespace IO
                          using IO::getch;
                          using IO::getstr;
                          using IO::putch;
                          using IO::putstr;
                          using IO::read;
                          using IO::write;
                          
                          bool mem1;
                          
                          #define maxn 50005
                          #define maxq 500005
                          
                          typedef pair<int, int> pii;
                          typedef tuple<int, int, int> tiii;
                          typedef tuple<int, int, int, int, int> tiiiii;
                          
                          vector<tiii> rec[2][maxn];
                          long long ans[maxq];
                          
                          class SegmentTree1 {
                             private:
                              class SegmentTree {
                                 private:
                                  struct Node {
                                      long long maxVal, maxVal_, lazy, lazy_;
                                      bool clearHist;
                                  };
                          
                                  Node tree[maxn << 4];
                                  int n;
                          
                                  void clearHist(int p) {
                                      if (tree[p].lazy_ || tree[p].lazy)
                                          calcLazy(p << 1, tree[p].lazy_, tree[p].lazy), calcLazy(p << 1 | 1, tree[p].lazy_, tree[p].lazy);
                                      return tree[p].maxVal_ = tree[p].maxVal, tree[p].lazy_ = tree[p].lazy = 0, tree[p].clearHist = true, void();
                                  }
                                  void calcLazy(int p, long long lazy_, long long lazy) {
                                      return tree[p].maxVal_ = max(tree[p].maxVal_, tree[p].maxVal + lazy_), tree[p].maxVal += lazy,
                                             tree[p].lazy_ = max(tree[p].lazy_, tree[p].lazy + lazy_), tree[p].lazy += lazy, void();
                                  }
                                  void pushDown(int p) {
                                      if (tree[p].clearHist) clearHist(p << 1), clearHist(p << 1 | 1), tree[p].clearHist = false;
                                      if (tree[p].lazy_ || tree[p].lazy)
                                          calcLazy(p << 1, tree[p].lazy_, tree[p].lazy), calcLazy(p << 1 | 1, tree[p].lazy_, tree[p].lazy),
                                              tree[p].lazy_ = tree[p].lazy = 0;
                                      return;
                                  }
                                  void pushUp(int p) {
                                      return tree[p].maxVal = max(tree[p << 1].maxVal, tree[p << 1 | 1].maxVal),
                                             tree[p].maxVal_ = max(tree[p << 1].maxVal_, tree[p << 1 | 1].maxVal_), void();
                                  }
                                  void add(int p, int l, int r, int ql, int qr, long long v) {
                                      if (ql <= l && r <= qr) return calcLazy(p, max(0LL, v), v);
                                      pushDown(p);
                                      int mid = (l + r) >> 1;
                                      if (ql <= mid) add(p << 1, l, mid, ql, qr, v);
                                      if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v);
                                      return pushUp(p);
                                  }
                                  void clearHist(int p, int l, int r, int ql, int qr) {
                                      if (ql <= l && r <= qr) return clearHist(p);
                                      pushDown(p);
                                      int mid = (l + r) >> 1;
                                      if (ql <= mid) clearHist(p << 1, l, mid, ql, qr);
                                      if (qr > mid) clearHist(p << 1 | 1, mid + 1, r, ql, qr);
                                      return pushUp(p);
                                  }
                          
                                  long long getHistMaxVal(int p, int l, int r, int ql, int qr) {
                                      if (ql <= l && r <= qr) return tree[p].maxVal_;
                                      pushDown(p);
                                      int mid = (l + r) >> 1;
                                      if (qr <= mid) return getHistMaxVal(p << 1, l, mid, ql, qr);
                                      if (ql > mid) return getHistMaxVal(p << 1 | 1, mid + 1, r, ql, qr);
                                      return max(getHistMaxVal(p << 1, l, mid, ql, qr), getHistMaxVal(p << 1 | 1, mid + 1, r, ql, qr));
                                  }
                          
                                 public:
                                  void resize(int _n) { return n = _n, void(); }
                                  void add(int l, int r, long long v) { return add(1, 1, n, l, r, v); }
                                  void clearHist(int l, int r) { return clearHist(1, 1, n, l, r); }
                                  long long getHistMaxVal(int l, int r) { return getHistMaxVal(1, 1, n, l, r); }
                              } ST;
                          
                              struct Node {
                                  vector<tiii> whole, init;
                                  vector<tiiiii> query;
                              };
                          
                              Node tree[maxn << 2];
                              int n;
                          
                              void insRec(int p, int l, int r, int ql, int qr, tiii v) {
                                  if (ql <= l && r <= qr) return tree[p].whole.push_back(v);
                                  int mid = (l + r) >> 1;
                                  if (ql <= mid && mid <= qr) tree[p].init.push_back(v);
                                  if (ql <= mid) insRec(p << 1, l, mid, ql, qr, v);
                                  if (qr > mid) insRec(p << 1 | 1, mid + 1, r, ql, qr, v);
                                  return;
                              }
                              void insQues(int p, int l, int r, tiiiii ques) {
                                  int mid = (l + r) >> 1;
                                  if ((l <= get<0>(ques) && get<0>(ques) <= mid && mid < get<1>(ques) && get<1>(ques) <= r) || l == r)
                                      return tree[p].query.push_back(ques);
                                  return get<1>(ques) <= mid ? insQues(p << 1, l, mid, ques) : insQues(p << 1 | 1, mid + 1, r, ques);
                              }
                              void solve(int p, int l, int r) {
                                  if (l == r) {
                                      for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), get<2>(i));
                                      ST.clearHist(1, n);
                                      for (auto i : tree[p].query) ans[get<4>(i)] = max(ans[get<4>(i)], ST.getHistMaxVal(get<2>(i), get<3>(i)));
                                      for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), -get<2>(i));
                                      return;
                                  }
                                  for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), get<2>(i));
                                  int mid = (l + r) >> 1;
                                  for (auto i : tree[p].init) ST.add(get<0>(i), get<1>(i), get<2>(i));
                                  static vector<tiii> cache;
                                  cache.clear(), ST.clearHist(1, n);
                                  sort(tree[p].query.begin(), tree[p].query.end(), [](tiiiii a, tiiiii b) { return get<0>(a) > get<0>(b); });
                                  auto j = tree[p].query.begin();
                                  while (j != tree[p].query.end() && get<0>(*j) == mid)
                                      ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++;
                                  for (int i = mid - 1; i >= l; i--) {
                                      for (auto j : rec[0][i + 1])
                                          ST.add(get<0>(j), get<1>(j), -get<2>(j)), cache.emplace_back(get<0>(j), get<1>(j), -get<2>(j));
                                      for (auto j : rec[1][i]) ST.add(get<0>(j), get<1>(j), get<2>(j)), cache.push_back(j);
                                      while (j != tree[p].query.end() && get<0>(*j) == i)
                                          ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++;
                                  }
                                  for (auto i = cache.rbegin(); i != cache.rend(); i++) ST.add(get<0>(*i), get<1>(*i), -get<2>(*i));
                                  cache.clear(), ST.clearHist(1, n);
                                  sort(tree[p].query.begin(), tree[p].query.end(), [](tiiiii a, tiiiii b) { return get<1>(a) < get<1>(b); });
                                  j = tree[p].query.begin();
                                  while (j != tree[p].query.end() && get<1>(*j) == mid)
                                      ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++;
                                  for (int i = mid + 1; i <= r; i++) {
                                      for (auto j : rec[1][i - 1])
                                          ST.add(get<0>(j), get<1>(j), -get<2>(j)), cache.emplace_back(get<0>(j), get<1>(j), -get<2>(j));
                                      for (auto j : rec[0][i]) ST.add(get<0>(j), get<1>(j), get<2>(j)), cache.push_back(j);
                                      while (j != tree[p].query.end() && get<1>(*j) == i)
                                          ans[get<4>(*j)] = max(ans[get<4>(*j)], ST.getHistMaxVal(get<2>(*j), get<3>(*j))), j++;
                                  }
                                  for (auto i = cache.rbegin(); i != cache.rend(); i++) ST.add(get<0>(*i), get<1>(*i), -get<2>(*i));
                                  for (auto i : tree[p].init) ST.add(get<0>(i), get<1>(i), -get<2>(i));
                                  solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r);
                                  for (auto i : tree[p].whole) ST.add(get<0>(i), get<1>(i), -get<2>(i));
                                  return;
                              }
                          
                             public:
                              void resize(int _n) { return n = _n, void(); }
                              void insRec(int l, int r, tiii v) { return insRec(1, 1, n, l, r, v); }
                              void insQues(tiiiii ques) { return insQues(1, 1, n, ques); }
                              void solve(void) { return ST.resize(n), solve(1, 1, n); }
                          } ST;
                          
                          void solve(void) {
                              ios::sync_with_stdio(false);
                              int n = read<int>(), m = read<int>(), q = read<int>();
                              ST.resize(n);
                              for (int i = 1; i <= m; i++) {
                                  int l1 = read<int>(), r1 = read<int>(), l2 = read<int>(), r2 = read<int>(), x = read<int>();
                                  rec[0][l1].emplace_back(r1, r2, x), rec[1][l2].emplace_back(r1, r2, x), ST.insRec(l1, l2, {r1, r2, x});
                              }
                              for (int i = 1; i <= q; i++) {
                                  int l1 = read<int>(), r1 = read<int>(), l2 = read<int>(), r2 = read<int>();
                                  ST.insQues({l1, l2, r1, r2, i});
                              }
                              ST.solve();
                              for (int i = 1; i <= q; i++) write(ans[i]), putch('n');
                              return;
                          }
                          
                          bool mem2;
                          
                          int main() {
                          #ifdef MACESUTED
                              cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
                          #endif
                          
                              int _ = 1;
                              while (_--) solve();
                          
                          #ifdef MACESUTED
                              cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
                          #endif
                              return 0;
                          }
                          
                          👍 2
                          • @ 2022-3-15 11:18:23

                            #017 2022.3.15

                            [APIO2016] 烟火表演

                            标签:动态规划,可合并堆,凸包。

                            题意

                            给定一颗树,称其的叶子节点为关键点 w1....mw_{1....m}. 同时给定树上每条边边权,你可以调整一条边的边权由 xyx \to y,其中需要花费 xy|x - y| 的代价。 你的目标是满足下列条件: (wi,wj),dis(wi,LCA(wi,wj))=dis(wj,LCA(wi,wj))\forall (w_i,w_j),dis(w_i,LCA(w_i,w_j)) = dis(w_j,LCA(w_i,w_j))

                            题解

                            分析

                            先考虑基础的做法。

                            fi,jf_{i,j} 表示 ii 的子树内所有叶子到 ii 的距离为 jj 的最小代价。

                            不妨将此 dpdp 看作一个函数,可知其为一个下凸函数。

                            我们再来思考一下如何把 fi,...f_{i,...} 这个函数转成给父亲的贡献 (因为要考虑 (i,fai)(i,fa_i) 这条边的权),我们设其为 gi,...g_{i,...}.

                            那可知 fu,...=gv,...f_{u,...} = \sum g_{v,...}

                            那我们只要考虑如何求出 gv,...g_{v,...}

                            考虑 fi,...f_{i,...} 为一个下凸壳,我们考虑记 [L,R][L,R]minfi,...\min f_{i,...}对应的下标。

                            那么有

                            l=val(i,fai)l = val(i,fa_i)

                            gi,x={fi,x+lxLfi,L+(l(xL))L<xL+lfi,LL+l<xR+lri,L+((xR)L)R+l<xg_{i,x}= \left\{ \begin{array}{rcl} f_{i,x} + l & & {x\leq L}\\ f_{i,L} + (l - (x - L)) & & {L<x\leq L + l}\\ f_{i,L} & & {L + l < x\leq R + l}\\ r_{i,L} + ((x - R) - L) & & {R + l < x} \end{array} \right.

                            我们思考这四种操作的本质。

                            我们将 L\leq L 的部分向上平移了 ll 个单位,将 [L,R][L,R] 的部分向右平移了 ll 单位,插入了一条 [L,L+r][L,L + r] 上斜率为 1-1 的直线,将 >R+l> R + l的部分改为 11.

                            bjLF3V.png

                            考虑各个转折点的位置间的斜率每次递增 11 (假如有一个斜率不存在,我们将这个转折点复制一个,表示不存在的斜率),我们只存下转折点。

                            那么我们合并时只要把转折点移动,并合并儿子即可。

                            最后计算答案时,显然 f1,0=lif_{1,0} = \sum l_i,那么可以遍历转折点找到最低段就能算出答案了。

                            代码

                            //晦暗的宇宙,我们找不到光,看不见尽头,但我们永远都不会被黑色打倒。——Quinn葵因
                            #include <bits/stdc++.h>
                            #define int long long
                            using namespace std;
                            int n, m, ans, tot;
                            int a[600010], f[600010], L[600010], deg[600010], rt[600010], l[600010], r[600010], dis[600010];
                            int read() {
                                int r = 0, f = 1;
                                char c = getchar();
                            
                                while (c < '0' || c > '9') {
                                    if (c == '-')
                                        f = -1;
                            
                                    c = getchar();
                                }
                            
                                while (c <= '9' && c >= '0')
                                    r = (r << 1) + (r << 3) + c - '0', c = getchar();
                            
                                return r * f;
                            }
                            void put(int x) {
                                if (x < 0) {
                                    putchar('-');
                                    x = ~x + 1;
                                }
                            
                                if (x > 9)
                                    put(x / 10);
                            
                                putchar(x % 10 + '0');
                            }
                            int merge(int x, int y) {
                                if (!x || !y)
                                    return x + y;
                            
                                if (a[x] < a[y])
                                    swap(x, y);
                            
                                r[x] = merge(r[x], y);
                            
                                if (dis[l[x]] < dis[r[x]])
                                    swap(l[x], r[x]);
                            
                                dis[x] = dis[r[x]] + 1;
                                return x;
                            }
                            int pop(int x) {
                                return merge(l[x], r[x]);
                            }
                            signed main() {
                                n = read(), m = read();
                            
                                for (int i = 2; i <= n + m; i++)
                                    f[i] = read(), L[i] = read(), deg[f[i]]++, ans += L[i];
                            
                                for (int i = n + m; i > 1; i--) {
                                    int l = 0, r = 0;
                            
                                    if (i <= n) {
                                        deg[i]--;
                            
                                        while (deg[i])
                                            deg[i]--, rt[i] = pop(rt[i]);
                            
                                        r = a[rt[i]], rt[i] = pop(rt[i]);
                                        l = a[rt[i]], rt[i] = pop(rt[i]);
                                    }
                            
                                    a[++tot] = l + L[i], a[++tot] = r + L[i];
                                    rt[i] = merge(rt[i], merge(tot - 1, tot));
                                    rt[f[i]] = merge(rt[f[i]], rt[i]);
                                }
                            
                                while (deg[1])
                                    deg[1]--, rt[1] = pop(rt[1]);
                            
                                while (rt[1])
                                    ans -= a[rt[1]], rt[1] = pop(rt[1]);
                            
                                put(ans);
                                puts("");
                                return 0;
                            }
                            
                            👍 2
                            ❤️ 1
                            • @ 2022-3-12 8:00:50

                              #016 2022.3.12

                              [CTSC2018]暴力写挂

                              标签:点分治,虚树,动态规划。

                              题意

                              给定两颗以11为根的树A,BA,B,其树边带权。定义点对 (i,j)(i,j) 的权值为两点到 11 的距离减去两点在 A,BA,B 两树上的LCALCA到对应树根 11 的距离,求出最大的点对的权值。 使用形式化的语言即求 maxdepA(i)+depA(j)depA(LCAA(i,j))depB(LCAB(i,j))depA(i)=disA(1,i),depB(i)=disB(1,i)\max dep_A(i) + dep_A(j) - dep_A(LCA_A(i,j)) - dep_B(LCA_B(i,j))\\dep_A(i) = dis_A(1,i),dep_B(i) = dis_B(1,i)

                              n366666,v2017011328n \leq 366666,|v| \leq 2017011328

                              题解

                              分析

                              考虑这种形式我们较难处理,我们一个自然的想法是把信息压缩下来,我们不妨把 depA(i),depA(j),depA(LCAA(i,j))dep_A(i),dep_A (j),dep_A(LCA_A(i,j)) 压缩成一种信息即 disA(i,j)dis_A(i,j)

                              那么有改写形式为 12maxdisA(i,j)+depA(i)+depA(j)2depB(LCAB(i,j))\frac{1}{2}\max dis_A(i,j) + dep_A(i) + dep_A(j) - 2*dep_B(LCA_B(i,j)),我们发现这样更改的一个显著进步即我们把从原本的两个非线性关系 (depA(LCAA(i,j)),depB(LCAB(i,j)))(dep_A(LCA_A(i,j)),dep_B(LCA_B(i,j))) 变成了只剩后者,考虑 depA(i),depA(j)dep_A(i),dep_A(j) 可类比于常数,那我们要做的实际上是在限定 dis(i,j)dis(i,j) 的同时,在 BB 这颗树上做一类点对统计问题。 考虑限制dis(i,j)dis(i,j)的一个经典的方法,我们使用点分治,那么我们发现dis(i,j)dis(i,j)同样可以拆贡献到点,设我们当前的分治中心为midmid,那么把 dis(i,j)=dis(i,mid)+dis(mid,j)dis(i,j) = dis(i,mid) + dis(mid,j) 就能把这个权值分配到点上,那么我们此时要做的任务即在 BB 上枚举 LCALCA,在其不同子树里找到 val(i)+val(j)val(i) + val(j) 的最大值即能用 val(i)+val(j)2depB(LCA),val(x)=depA(x)+dis(x,mid)val(i) + val(j) - 2 * dep_B(LCA),val(x) = dep_A(x) + dis(x,mid) 更新答案。

                              但是我们还有一些限制:

                              一:首先,我们选择的 BB 子树里的 i,ji,j 必须在 midmid 分属两侧,即其要跨越 midmid,我们把 midmid 的每一个子树内的点染上不同颜色即可,在BB中上进行树上动态规划,维护其子树内的权值最大点 与 和最大权值对应点的颜色不一样的权值次大点,在儿子更新父亲的这两点时更新答案。

                              二:我们显然不能每次分治都进行一个满的 O(n)O(n) 的树上动态规划,否则时间复杂度将退化为 O(n2)O(n^2),但我们发现,我们称点分治时 midmid 管理的点为关键点,我们可以在 BB 上构建这些关键点对应的虚树,那么直接对虚树进行dpdp 即可,由于虚树大小和关键点点集大小线性相关,所以保证了复杂度。

                              代码

                              //晦暗的宇宙,我们找不到光,看不见尽头,但我们永远都不会被黑色打倒。——Quinn葵因
                              #include <bits/stdc++.h>
                              #define ll long long
                              #define N 1000000
                              using std::vector;
                              using std::pair;
                              
                              int n;
                              
                              #define pil pair<int,ll>
                              #define mp std::make_pair
                              
                              vector<pil>A[N], B[N]; //tree
                              
                              ll depa[N], depb[N];
                              int dep[N];
                              
                              inline void dfsa(int u, int fa) {
                                  for (auto it : A[u]) {
                                      int x = it.first;
                                      ll v = it.second;
                                      if (x == fa)
                                          continue;
                                      depa[x] = depa[u] + v;
                                      dfsa(x, u);
                                  }
                              }
                              
                              int F[N][20];
                              
                              int dfn[N];
                              int cnt;
                              
                              inline void dfsb(int u, int fa) {
                                  F[u][0] = fa;
                                  dep[u] = dep[fa] + 1;
                                  for (int i = 1; i <= 19; ++i)
                                      F[u][i] = F[F[u][i - 1]][i - 1];
                                  dfn[u] = ++cnt;
                                  for (auto it : B[u]) {
                                      int x = it.first;
                                      ll v = it.second;
                                      if (x == fa)
                                          continue;
                                      depb[x] = depb[u] + v;
                                      dfsb(x, u);
                                  }
                              }
                              
                              int sum, siz[N], root;
                              int maxn[N];
                              
                              ll val[N];
                              int c[N];
                              int vis[N];
                              
                              inline void find(int u, int fa) {
                                  siz[u] = 1;
                                  maxn[u] = 1;
                                  for (auto it : A[u]) {
                                      int v = it.first;
                                      if (v == fa || vis[v])
                                          continue;
                                      find(v, u);
                                      siz[u] += siz[v];
                                      maxn[u] = std::max(maxn[u], siz[v]);
                                  }
                                  maxn[u] = std::max(maxn[u], sum - siz[u]);
                                  if (maxn[u] < maxn[root])
                                      root = u;
                              }
                              
                              vector<int>P;
                              
                              inline void dis(int u, int fa) {
                                  c[u] = c[fa];
                                  for (auto it : A[u]) {
                                      int v = it.first;
                                      ll vi = it.second;
                                      if (vis[v] || v == fa)
                                          continue;
                                      val[v] = val[u] + vi;
                                      dis(v, u);
                                  }
                                  val[u] = val[u] + depa[u];
                                  P.push_back(u);
                              }
                              
                              inline int lca(int x, int y) {
                                  if (dep[x] < dep[y])
                                      std::swap(x, y);
                                  for (int i = 19; i >= 0; --i) {
                                      if (dep[F[x][i]] >= dep[y])
                                          x = F[x][i];
                                  }
                                  if (x == y)
                                      return x;
                                  for (int i = 19; i >= 0; --i) {
                                      if (F[x][i] != F[y][i])
                                          x = F[x][i], y = F[y][i];
                                  }
                              
                                  return F[x][0];
                              }
                              
                              inline bool cmp(int x, int y) {
                                  return dfn[x] < dfn[y];
                              }
                              
                              ll f[N][2];
                              
                              bool key[N];
                              
                              int Fi[N];
                              
                              ll ans = -1e18;
                              
                              #define pii pair<ll,int>
                              
                              vector<pii>M;
                              
                              inline void merge(int x, int y) { //y -> x
                                  for (int i = 0; i < 2; ++i)
                                      for (int j = 0; j < 2; ++j)
                                          if (c[f[x][i]] != c[f[y][j]])
                                              ans = std::max(ans, val[f[x][i]] + val[f[y][j]] - 2 * depb[x]);
                                  M.clear();
                                  M.push_back(mp(-val[f[x][0]], f[x][0]));
                                  M.push_back(mp(-val[f[x][1]], f[x][1]));
                                  M.push_back(mp(-val[f[y][0]], f[y][0]));
                                  M.push_back(mp(-val[f[y][1]], f[y][1]));
                                  std::sort(M.begin(), M.end());
                                  f[x][0] = M[0].second;
                              
                                  for (int i = 1; i <= 3; ++i) {
                                      if (c[M[i].second] != c[f[x][0]]) {
                                          f[x][1] = M[i].second;
                                          return ;
                                      }
                                  }
                              }
                              
                              inline int iread(){
                                 int s=0,w=1;
                                 char ch=getchar();
                                 while(ch<'0'||ch>'9'){ch=getchar();}
                                 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
                                 return s*w;
                              }
                              
                              inline ll lread(){
                                 ll s=0,w=1;
                                 char ch=getchar();
                                 while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
                                 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
                                 return s*w;
                              }
                              
                              inline void build() {
                                  val[0] = -1e18;
                                  c[0] = -1;
                                  std::sort(P.begin(), P.end(), cmp);
                                  for (int i = 0; i < P.size(); ++i)
                                      key[P[i]] = 1;
                                  int k = P.size();
                                  for (int i = 1; i < k; ++i)
                                      P.push_back(lca(P[i], P[i - 1]));
                                  std::sort(P.begin(), P.end(), cmp);
                                  P.erase(unique(P.begin(), P.end()), P.end());
                                  for (int i = 1; i < P.size(); ++i)
                                      Fi[P[i]] = lca(P[i], P[i - 1]);
                                  for (int i = 0; i < P.size(); ++i) {
                                      if (!key[P[i]])
                                          f[P[i]][0] = f[P[i]][1] = 0;
                                      else
                                          f[P[i]][0] = P[i], f[P[i]][1] = 0;
                                  }
                                  for (int i = P.size() - 1; i >= 1; --i) {
                                      int u = P[i];
                                      merge(Fi[u], u);
                                  }
                                  for (int i = 0; i < P.size(); ++i)
                                      key[P[i]] = 0;
                              }
                              
                              inline void solve(int u) {
                                  vis[u] = 1;
                                  find(u, 0);
                                  val[u] = depa[u];
                                  c[u] = u;
                                  P.clear();
                                  P.push_back(u);
                                  for (auto it : A[u]) {
                                      int v = it.first;
                                      ll vi = it.second;
                                      if (vis[v])
                                          continue;
                                      val[v] = vi;
                                      c[v] = v;
                                      dis(v, v);
                                  }
                                  build();
                                  for (auto it : A[u]) {
                                      int v = it.first;
                                      sum = siz[v], root = 0;
                                      if (vis[v])
                                          continue;
                                      find(v, 0);
                                      solve(root);
                                  }
                              }
                              
                              signed main() {
                                  //  freopen("q.in","r",stdin);
                                  //  freopen("q.out","w",stdout);
                              //    scanf("%d", &n);
                              	n = iread();
                                  for (int i = 1; i < n; ++i) {
                                      int x = iread(), y = iread();
                                      ll v = lread();
                                      A[x].push_back(mp(y, v));
                                      A[y].push_back(mp(x, v));
                                  }
                              
                                  for (int i = 1; i < n; ++i) {
                                      int x = iread(), y = iread();
                                      ll v = lread();
                                      B[x].push_back(mp(y, v));
                                      B[y].push_back(mp(x, v));
                                  }
                              
                                  dfsa(1, 0);
                                  dfsb(1, 0);
                                  maxn[0] = n * 2;
                                  root = 0;
                                  sum = n;
                                  find(1, 0);
                                  solve(root);
                                  ans = ans / 2;
                              
                                  for (int i = 1; i <= n; ++i)
                                      ans = std::max(ans, 2ll * depa[i] - depa[i] - depb[i]);
                              
                                  std::cout << ans << "\n";
                              }
                              
                              /*
                              6
                              1 2 2
                              1 3 0
                              2 4 1
                              2 5 -7
                              3 6 0
                              1 2 -1
                              2 3 -1
                              2 5 3
                              2 6 -2
                              3 4 8
                              */
                              
                              👍 4
                              • @ 2022-3-4 7:16:04

                                #015 2022.3.4

                                CF1500F Cupboards Jumps

                                标签:动态规划,构造。

                                题意

                                给出长度为 n2n - 2 的数组 wiw_i,请你构造一个长度为 nn 的数组 aa 满足 i[1, n2], max(ai, ai+1, ai+2)min(ai, ai+1, ai+2)=wi\forall i \in [1,~n - 2],~\max(a_i,~a_{i + 1},~a_{i + 2}) - \min(a_i,~a_{i + 1},~a_{i + 2}) = w_i。若不能构造输出 NO

                                n106, 0wi1012, 0ai1018n \le 10^6,~0 \le w_i \le 10^{12},~0 \le a_i \le 10^{18}

                                题解

                                分析

                                考虑令 ci=ai+1aic_i = a_{i + 1} - a_i,则 wi=max(ci, ci+1, ci+ci+1)w_i = \max(|c_i|,~|c_{i + 1}|,~|c_i + c_{i + 1}|)

                                在确定 cic_i 考虑 wiw_ici+1c_{i + 1} 的限制时我们发现,我们可以通过将 a1ai+1a_1 \sim a_{i + 1} 全部乘上 1-1 以使得 c1cic_1 \sim c_i 全都乘上 1-1,容易发现这并不会影响 w1wi1w_1 \sim w_{i - 1} 带来的所有限制。因此我们发现我们在研究该限制时并不关心 cic_i 的符号,我们令 di=cid_i = |c_i|,则 wi=max(di, di+1, di+di+1)w_i = \max(d_i,~d_{i + 1},~d_i + d_{i + 1})

                                考虑对该限制分别考虑最大值在哪一项上取到。设状态 fi, jf_{i,~j} 表示考虑了 d1did_1 \sim d_i,且 di=jd_i = j 的方案是否合法。则对于所有合法情况 fi, jf_{i,~j},有:

                                1. j=wij = w_i,则 k[0, wi], fi+1, k=True\forall k \in [0,~w_i],~f_{i + 1,~k} = \text{True}
                                2. 0<jwi0 < j \le w_i,则 fi+1, wi=Truef_{i + 1,~w_i} = \text{True}
                                3. 0<jwi0 < j \le w_ifi+1, wij=Truef_{i + 1,~w_i - j} = \text{True}

                                仔细观察,我们发现若 fi, wi=Truef_{i,~w_i} = \text{True}fi+1f_{i + 1} 数组中全部能取到的部分都为 True\text{True},不需要考虑其他两个情况;若 fif_{i} 数组中存在一项为 True\text{True} 那么 fi+1, wif_{i + 1,~w_i}True\text{True}。这两种情况均可快速判断,而情况 3 则需要将所有合法状态 jj 转换为 wijw_i - j

                                考虑维护 fif_i 数组中连续的 True\text{True} 段,则对于一个段 [l, r][l,~r],其转移后为 [wir, wil][w_i - r,~w_i - l]。容易发现其由一个翻转操作和一个平移操作构成。因此每次从 ii 转移到 i+1i + 1 时,只需判断情况 1 和 2,然后再全局修改连续段的翻转和平移情况即可。若在转移到 n1n - 1 前连续段集合为空,则无解,否则有解。

                                考虑如何构造 dd 数组。我们可以在最终的连续段集合中任取一个点的值作为 dn1d_{n - 1},考虑从后往前构造出整个 dd 数组,发现只有三种情况:

                                1. did_i 可以等于 wiw_i,则令 di=wid_i = w_i。因为若 di=wid_i = w_i,则 di+1d_{i + 1} 可以取任意可以取到的值,所以这么做并不会影响正确性。
                                2. di+1=wid_{i + 1} = w_i,则令 did_i 为任意可以取到的小于 wiw_i 的值。
                                3. 若不满足上面的两个条件,则令 di=widi+1d_i = w_i - d_{i + 1}

                                需要注意的是这里需要用到“任意可以取到的小于 wiw_i 的值”,这需要实现中在转移 ff 时提前记录该项和 did_i 能否取到 wiw_i 值。

                                构造完 dd 数组后,考虑如何构造 cc。这则相对简单,判断 di+di+1d_i + d_{i + 1} 是否等于 wiw_i。若不等于,则 cic_ici+1c_{i + 1} 需异号,否则需同号。

                                最后根据 cc 数组随意构造出满足每个元素均为非负整数的 aa 数组即可。

                                代码

                                View On GitHub

                                /**
                                 * @file 1500F.cpp
                                 * @author Macesuted (i@macesuted.moe)
                                 * @date 2022-03-03
                                 *
                                 * @copyright Copyright (c) 2022
                                 * @brief
                                 *      My Tutorial: https://macesuted.moe/article/cf1500f
                                 *
                                 */
                                
                                #include <bits/stdc++.h>
                                using namespace std;
                                
                                namespace io {
                                #define SIZE (1 << 20)
                                char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
                                int f, qr;
                                inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
                                inline char getch(void) {
                                    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
                                }
                                void putch(char x) {
                                    *oS++ = x;
                                    if (oS == oT) flush();
                                    return;
                                }
                                string getstr(void) {
                                    string s = "";
                                    char c = getch();
                                    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
                                    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
                                    return s;
                                }
                                void putstr(string str, int begin = 0, int end = -1) {
                                    if (end == -1) end = str.size();
                                    for (int i = begin; i < end; i++) putch(str[i]);
                                    return;
                                }
                                template <typename T>
                                T read() {
                                    T x = 0;
                                    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
                                        if (c == '-') f = -1;
                                    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
                                    return x * f;
                                }
                                template <typename T>
                                void write(const T& t) {
                                    T x = t;
                                    if (!x) putch('0');
                                    if (x < 0) putch('-'), x = -x;
                                    while (x) qu[++qr] = x % 10 + '0', x /= 10;
                                    while (qr) putch(qu[qr--]);
                                    return;
                                }
                                struct Flusher_ {
                                    ~Flusher_() { flush(); }
                                } io_flusher_;
                                }  // namespace io
                                using io::getch;
                                using io::getstr;
                                using io::putch;
                                using io::putstr;
                                using io::read;
                                using io::write;
                                
                                bool mem1;
                                
                                #define maxn 1000005
                                
                                typedef pair<long long, long long> pll;
                                
                                long long a[maxn], d[maxn], w[maxn], v[maxn], limd[maxn];
                                set<pll> S;
                                
                                void solve(void) {
                                    int n = read<int>();
                                    long long C = read<long long>();
                                    for (int i = 1; i < n; i++) limd[i] = numeric_limits<long long>::max();
                                    for (int i = 1; i <= n - 2; i++)
                                        w[i] = read<long long>(), limd[i] = min(limd[i], w[i]), limd[i + 1] = min(limd[i + 1], w[i]);
                                    S.emplace(0, limd[1]);
                                    long long A = +1, B = 0;
                                    for (int i = 1; i <= n - 1; i++) {
                                        if (A == +1) {
                                            while (!S.empty() && S.rbegin()->first + B > limd[i]) S.erase(--S.end());
                                            if (!S.empty() && S.rbegin()->second + B > limd[i]) {
                                                int l = S.rbegin()->first;
                                                S.erase(--S.end()), S.emplace(l, limd[i] - B);
                                            }
                                        } else {
                                            while (!S.empty() && -S.begin()->second + B > limd[i]) S.erase(S.begin());
                                            if (!S.empty() && -S.begin()->second + B > limd[i]) {
                                                int r = S.begin()->second;
                                                S.erase(S.begin()), S.emplace(B - limd[i], r);
                                            }
                                        }
                                        long long tw = (w[i] - B) / A;
                                        auto p = S.lower_bound({tw + 1, tw + 1});
                                        if (p != S.begin() && (--p)->second >= tw) {
                                            v[i] = w[i];
                                            S.clear(), S.emplace(0, limd[i + 1]), A = +1, B = 0;
                                            continue;
                                        }
                                        if (S.empty()) return putstr("NO\n");
                                        v[i] = S.begin()->first * A + B;
                                        if (i == n - 1) break;
                                        A = -A, B = w[i] - B;
                                        tw = (w[i] - B) / A;
                                        p = S.lower_bound({tw + 1, tw + 1});
                                        if (p == S.begin() || (--p)->second < tw) S.emplace(tw, tw);
                                    }
                                    d[n - 1] = v[n - 1];
                                    putstr("YES\n");
                                    for (int i = n - 2; i; i--)
                                        if (v[i] == w[i])
                                            d[i] = w[i];
                                        else if (d[i + 1] == w[i])
                                            d[i] = v[i];
                                        else
                                            d[i] = abs(w[i] - d[i + 1]);
                                    long long minVal = 0, pre = 0;
                                    for (int i = 2, id = +1; i <= n - 1; i++) {
                                        if (abs(d[i - 1]) + abs(d[i]) != w[i - 1]) id = -id;
                                        d[i] *= id;
                                        minVal = min(minVal, pre += d[i]);
                                    }
                                    a[1] = -minVal;
                                    for (int i = 2; i <= n; i++) a[i] = a[i - 1] + d[i - 1];
                                    for (int i = 1; i <= n; i++) write(a[i]), putch(" \n"[i == n]);
                                    return;
                                }
                                
                                bool mem2;
                                
                                int main() {
                                #ifdef MACESUTED
                                    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
                                #endif
                                
                                    int _ = 1;
                                    while (_--) solve();
                                
                                #ifdef MACESUTED
                                    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
                                #endif
                                    return 0;
                                }
                                
                                👍 7
                                • @ 2022-2-24 21:23:17

                                  #014 2022.2.24

                                  CF1307G Cow and Exercise

                                  标签:线性规划,网络流。

                                  题意

                                  给出一个 nn 个点 mm 条边的有向有边权图。你可以对任意一条边执行操作使得该边边权加一。有 qq 个询问,每个询问给出一个 xx,求在操作次数不超过 xx 的情况下 11nn 最短路的最大值。

                                  n50, mn×(n1), wi106, q105, x105n \le 50,~m \le n \times (n-1),~w_i \le 10^6,~q \le 10^5,~x \le 10^5

                                  题解

                                  分析

                                  先按照最短路定义以及题目要求列出不等式:

                                  maximize dnd1{djdiai, jwi, jai, jxdi, ai, j0\text{maximize}~d_n - d_1 \\ \begin{cases} d_j - d_i - a_{i,~j} \le w_{i,~j} \\ \sum a_{i,~j} \le x \\ d_i,~a_{i,~j} \ge 0 \end{cases}

                                  n=3n = 3 为例可以画出下面的线性规划矩阵:

                                  d1d2d3a1, 2a1, 3a2, 1a2, 3a3, 1a3, 21+10100000w1, 210+1010000w1, 3+110001000w2, 101+1000100w2, 3+101000010w3, 10+11000001w3, 2000+1+1+1+1+1+1x10+1000000Ans\begin{array}{ccccccccccc} d_1 & d_2 & d_3 & a_{1,~2} & a_{1,~3} & a_{2,~1} & a_{2,~3} & a_{3,~1} & a_{3,~2} & & \\ \hline -1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \le & w_{1,~2} \\ -1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & \le & w_{1,~3} \\ +1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & \le & w_{2,~1} \\ 0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & \le & w_{2,~3} \\ +1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & \le & w_{3,~1} \\ 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & \le & w_{3,~2} \\ 0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & \le & x \\ -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & \ge & Ans \\ \end{array}

                                  我们纵向看该矩阵求出其对偶线性规划:

                                  p1, 21+10100000w1, 2p1, 310+1010000w1, 3p2, 1+110001000w2, 1p2, 301+1000100w2, 3p3, 1+101000010w3, 1p3, 20+11000001w3, 2q000+1+1+1+1+1+1x10+1000000Ans\begin{array}{c|cccccccccc} p_{1,~2} & -1 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & w_{1,~2} \\ p_{1,~3} & -1 & 0 & +1 & 0 & -1 & 0 & 0 & 0 & 0 & w_{1,~3} \\ p_{2,~1} & +1 & -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & w_{2,~1} \\ p_{2,~3} & 0 & -1 & +1 & 0 & 0 & 0 & -1 & 0 & 0 & w_{2,~3} \\ p_{3,~1} & +1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & w_{3,~1} \\ p_{3,~2} & 0 & +1 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & w_{3,~2} \\ q & 0 & 0 & 0 & +1 & +1 & +1 & +1 & +1 & +1 & x \\ & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \ge & \le \\ & -1 & 0 & +1 & 0 & 0 & 0 & 0 & 0 & 0 & Ans \\ \end{array}

                                  即:

                                  minimize (wi, j×pi, j)+x×q{jpj, ijpi, j{1,i=10,1<i<n+1,i=npi, j+q0pi, j, q0\text{minimize}~ \bigg( \sum w_{i,~j} \times p_{i,~j} \bigg) + x \times q \\ \begin{cases} \sum_j p_{j,~i} - \sum_j p_{i,~j} \ge \begin{cases} -1,& i=1 \\ 0,& 1 < i < n \\ +1,& i=n \\ \end{cases}\\ -p_{i,~j} + q \ge 0 \\ p_{i,~j},~q \ge 0 \end{cases}

                                  发现其形式非常类似于最小费用最大流:令 pi, jp_{i,~j} 为边 iji \to j 流量,第一条不等式限制除 11nn 以外的其他所有结点入流量不超过出流量,且 11 号点出流量比入流量大 11nn 号点入流量比出流量大 11;第二条不等式限制每条边流量均不超过上限 qq