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

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

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

43 comments

  • @ 2023-9-3 12:38:20

    mcrOJ规则怪谈世界你好,有兴趣忙

    • @ 2023-9-2 10:04:48

      Hydro每年一题。。。。。。。

      • @ 2022-10-7 12:18:36

        #041 2022.10.7

        POJ P1015 Jury Compromise

        Statement

        选一个陪审团,先随机挑选 nn 个人作为陪审团的候选人,然后选 mm 人组成陪审团。控方和辩方会给候选人打分。请做到选出的 mm 个人满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案,那么选辩控双方总分之和最大的方案。如果方案还是不惟一,输出任意一种均可。

        • n200n\le 200
        • m20,mnm\le 20,m\le n
        • 任何分值不超过 2020

        Tutorial

        Click to see

        虽然数据范围不大,以为是搜索,但其实是受了“宇宙射线”影响的超级变形背包。可能连一点背包的影子都不见了。

        考虑 DP。设状态 f(i,j,k)f(i,j,k) 表示前 ii 个人中选 jj 个人,得分差为 k400k-400,最大的得分总和。注意这里得分差不是绝对值差,为了防止下标出现负数,差需要加上 base=400base=400

        这道题难于找出答案的具体方案。在 DP 过程中,把所有不合法解全部标为负无穷,从 basebase 处剖开,不难发现,最终状态中找到的第一个合法状态,就是我们想要的。后面的倒退不难,注意输出格式。

        为什么这样就解决问题了呢?要求差最小,把 basebase 看作 00,也就是对于 v,vv,-v,如果状态 f(n,m,v+base)f(n,m,v+base) 合法,vv 的绝对值一定是最小的。至于和最大,DP 迭代过程中已经计算出来了。

        // 陪审团
        #include <iostream>
        #include <cstring>
        #include <vector>
        #include <cstdio>
        #include <algorithm>
        #define SIZE 205
        #define all(x) x.begin(), x.end()
        #define debug(x) cout<<#x<<":"<<x<<endl;
        using namespace std;
        
        int n, m; 
        int p[SIZE], d[SIZE];
        int base=400;
        int f[SIZE][21][1000];
        
        signed main()
        {
        	int COUNT=1;
        	while(cin>>n>>m && n+m)
        	{
        		for(int i=1; i<=n; i++) cin>>p[i]>>d[i];
        		memset(f, -0x3f, sizeof(f));
        		f[0][0][base]=0;
        		for(int i=1; i<=n; i++)
        			for(int j=0; j<=m; j++) 
        				for(int k=0; k<1000; k++)
        				{
        					int tmp=k-(p[i]-d[i]);
        					if(tmp<0 || tmp>=1000)
        					{
        						f[i][j][k]=f[i-1][j][k]; continue;
        					}
        					if(!j)
        					{
        						f[i][j][k]=f[i-1][j][k]; continue;
        					}
        					f[i][j][k]=max(f[i-1][j][k], f[i-1][j-1][tmp]+p[i]+d[i]);
        				}
        		int v=0;
                while(f[n][m][base-v]<0 && f[n][m][base+v]<0) v++;
                if(f[n][m][base-v]>f[n][m][base+v]) v=base-v;
                else v=base+v;
            	
                vector<int> ans;
                int i=n, j=m, k=v;
                while(j)
                {
                	if(f[i][j][k]==f[i-1][j][k]) i--;
                	else
                	{
                		ans.push_back(i); k-=(p[i]-d[i]);
                		i--, j--;
        			}
        		}
        		
        		int sp=0, sd=0;
        		for(int i=0; i<ans.size(); i++)
        			sp+=p[ans[i]], sd+=d[ans[i]];
        		printf("Jury #%d\n", COUNT++);
        		printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);
        		sort(all(ans));
        		for(int i=0; i<ans.size(); i++)
        			cout<<" "<<ans[i];
        		cout<<endl; cout<<endl;
        	}
        
            return 0;
        }
        
        👀 10
        👍 7
        🌿 4
        😄 3
        ❤️ 3
      • @ 2022-8-19 8:02:26

        #040 2022.8.19

        bzoj #4205. 卡牌配对

        Statement

        现在有一种卡牌游戏,每张卡牌上有三个属性值:A,B,CA,B,C

        把卡牌分为 X,YX,Y 两类,分别有 n1,n2n1,n2 张。

        两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。

        比如一张 XX 类卡牌属性值分别是 225,233,101225,233,101,一张 YY 类卡牌属性值分别为 115,466,99115,466,99

        那么这两张牌是可以配对的,因为只有 1011019999 一组属性互质。

        游戏的目的是最大化匹配上的卡牌组数,当然每张卡牌只能用一次。

        Data Range:1n1,n23×104\textbf{Data Range:} 1 \leq n1, n2 \leq 3 \times 10^4

        Solution

        solution 这道题有一个很直接的最大流做法,但是暴力建边的复杂度和边数都是 $n_1 \times n_2$ 的,于是要考虑优化建边的数量。

        注意到题目要求两张卡牌存在至多一项属性值使得两张卡牌该项属性值互质。

        这个要求等价于两张卡牌至少有两项属性值的 gcd\gcd 大于 11,也就是有至少一个相同的质因数。

        我们先暴力枚举这两项属性值是 AB,AC,BCAB,AC,BC 三种情况。

        我们分别枚举 XX 中这两个属性值的质因数,以及他们可能形成的组合,将这个质因数组合建出一个点 idid

        然后枚举 YY 中这两个属性值的质因数,以及他们可能形成的组合,查看之前枚举 XX 的时候是否有建出对应的点,如果有代表 XXYY 这两个属性值存在相同的质因数,也就满足了上面的要求。

        那么可以将这个东西进行网络流建模,我们假设左边 XX 中第 ii 张卡牌包含 idid 点所代表的质因数,右边第 jj 张卡牌也包含 idid 点所包含的质因数。

        那么我们可以 iidi \rightarrow id,流量为 11id(j+n1)id \rightarrow (j + n1),流量为 11

        如此对枚举的两项属性值是 AB,AC,BCAB,AC,BC 三种情况分别做一遍,然后设置一个源点和汇点与 X,YX,Y 卡牌分别连边,流量为 11,之后跑最大流即可。

        200200 以内的质数只有 4646 个,一个数最多 44 个质因子。

        我们中间新建出来的点数最多为 3×46×463 \times 46 \times 46,中间建出来的边数最多为 16(n1+n2)16(n1 +n2)

        // 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
        // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱!
        // 没有力量的理想是戏言,没有理想的力量是空虚
        #include <bits/stdc++.h>
        #define LL long long
        #define int long long
        using namespace std;
        char ibuf[1 << 15], *p1, *p2;
        #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++)
        inline int read() {
          char ch = getchar();  int x = 0, f = 1;
          while (ch < '0' || ch > '9')  {  if (ch == '-')  f = -1;  ch = getchar();  }
          while (ch >= '0' && ch <= '9')  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
          return x * f;
        }
        void print(LL x) {
          if (x > 9)  print(x / 10);
          putchar(x % 10 + '0');
        }
        template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
        template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
        #define rep(i, l, r) for (int i = (l); i <= (r); i++)
        #define repd(i, l, r) for (int i = (l); i >= (r); i--)
        #define REP(i, l, r)  for (int i = (l); i < (r); i++)
        const int N = 5e6;
        int pr[N], cnt, vis[N];
        void prime(int n) {
          rep (i, 2, n) {
            if (!vis[i]) {  pr[++cnt] = i;  }
            for (int j = i; j <= n; j += i)  vis[j] = 1;
          }
        }
        int n1, n2;
        map <pair<int,int>, int> id;
        int tot, S, T;
        int num = 1, nex[N], first[N], v[N], flow[N];
        vector <int> ys[205];
        int dep[N], cur[N];
        queue <int> q;
        struct node {  int a, b, c;  } X[N], Y[N];
        bool bfs(int s,int t) {
          rep (i, 0, t)  dep[i] = 0;
          q.push(s);  dep[s] = 1;
          while (!q.empty()) {
            int u = q.front();  q.pop();  cur[u] = first[u];
            for (int i = first[u]; i; i = nex[i]) {
              int to = v[i];
              if (dep[to] || !flow[i])  continue;
              q.push(to);  dep[to] = dep[u] + 1;  cur[to] = first[to];
            }
          }
          return dep[t] != 0;
        }
        int dfs(int x,int a) {
          if (x == T)  return a;
          int ans = 0;
          for (int i = cur[x]; i; i = nex[i]) {
            int to = v[i];
            cur[x] = i; 
            if (dep[to] == dep[x] + 1 && flow[i]) {
              int qwq = dfs(to, min(flow[i], a));
              a -= qwq;  flow[i] -= qwq;  flow[i ^ 1] += qwq;  ans += qwq;
              if (!a)  break;
            }
          }
          return ans;
        }
        int mxflow(int s,int t) {
          int ans = 0;
          while (bfs(s, t))  ans += dfs(s, 1ll << 30);
          return ans;
        }
        void add(int from,int to,int val) {
          nex[++num] = first[from];  first[from] = num;  v[num] = to;  flow[num] = val;
        }
        void ins(int a,int b,int c) {
          add(a, b, c), add(b, a, 0);
        }
        void solve() {
          prime(200);
          n1 = read(), n2 = read();
          rep (i, 1, n1) {  X[i].a = read(), X[i].b = read(), X[i].c = read();  }
          rep (i, 1, n2) {  Y[i].a = read(), Y[i].b = read(), Y[i].c = read();  }
          tot = n1 + n2;
          sort(pr + 1, pr + cnt + 1);
          rep (x, 1, 200) {
            rep (j, 1, cnt) {
              if (x < pr[j])  continue;
              if (x % pr[j] == 0)  ys[x].push_back(pr[j]);
            }
          }
          // AB
          id.clear();
          rep (i, 1, n1) {
            int A = X[i].a, B = X[i].b;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[{pp, qq}] == 0)  {
                  id[ {pp, qq} ] = ++tot;
                  // cout << 1 << " " << pp << " " << qq << " get id : " << tot << "\n";
                }
                int pt = id[ {pp, qq} ];
                ins(i, pt, 1);
              }
            }
          }
          rep (i, 1, n2) {
            int A = Y[i].a, B = Y[i].b;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[ {pp, qq} ] == 0) {
                  id[ {pp, qq} ] = ++tot;
                }
                int pt = id[ {pp, qq} ];
                ins(pt, i + n1, 1);
              }
            }
          }
          // AC
          id.clear();
          rep (i, 1, n1) {
            int A = X[i].a, B = X[i].c;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[{pp, qq}] == 0) { 
                  id[ {pp, qq} ] = ++tot;
                }
                int pt = id[ {pp, qq} ];
                ins(i, pt, 1);
              }
            }
          }
          rep (i, 1, n2) {
            int A = Y[i].a, B = Y[i].c;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[ {pp, qq} ] == 0) {
                  id[ {pp, qq} ] = ++tot;
                }
                int pt = id[ {pp, qq} ];
                ins(pt, i + n1, 1);
              }
            }
          }
          //BC
          id.clear();
          rep (i, 1, n1) {
            int A = X[i].b, B = X[i].c;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[{pp, qq}] == 0)  id[ {pp, qq} ] = ++tot;
                int pt = id[ {pp, qq} ];
                ins(i, pt, 1);
              }
            }
          }
          rep (i, 1, n2) {
            int A = Y[i].b, B = Y[i].c;
            for (auto p : ys[A]) {
              for (auto q : ys[B]) {
                int pp = p, qq = q;
                if (id[ {pp, qq} ] == 0) {
                  id[ {pp, qq} ] = ++tot;
                }
                int pt = id[ {pp, qq} ];
                ins(pt, i + n1, 1);
              }
            }
          }
          S = tot + 1, T = tot + 2;
          rep (i, 1, n1)  ins(S, i, 1);
          rep (i, 1, n2)  ins(i + n1, T, 1);
          int ans = mxflow(S, T);
          cout << ans << "\n";
        }
        signed main () {
        #ifdef LOCAL_DEFINE
          freopen("1.in", "r", stdin);
          freopen("1.ans", "w", stdout);
        #endif
          int T = 1;  while (T--)  solve();
        #ifdef LOCAL_DEFINE
          cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
        #endif
          return 0;
        }
        
        ❤️ 6
        👍 5
      • @ 2022-7-22 7:31:21

        #039 2022.7.22

        标签:倍增。

        Statement

        定义函数 ff 如下:

        f((l, r))=(mini=lrai, maxi=lrai)f\big((l,~r)\big) = (\min_{i = l}^r a_i,~\max_{i = l}^r a_i)

        给出长度为 nn 的值域为 1n1 \sim n 序列 aaqq 个询问,每次询问给出 li, ril_i,~r_i,问 (li, ri)(l_i,~r_i) 通过多少次 ff 操作后达到 (1, n)(1,~n),或判断无法达到。

        n, q105n,~q \le 10^5

        Solution

        Solution

        考虑对于一个点 pp,当其同时存在于 [l1, r1][l_1,~r_1][l2, r2][l_2,~r_2] 内时,由于 mini=l1r1aiapmaxi=l1r1ai\min_{i = l_1}^{r_1} a_i \le a_p \le \max_{i = l_1}^{r_1} a_i,所以 apf((l1, r1))a_p \in f\big((l_1,~r_1)\big),同理 apf((l2, r2))a_p \in f\big((l_2,~r_2)\big)。也就是说,当两个区间有交时,他们各进行一次 ff 操作后分别得到的两个新区间也同样有交。

        对于 [l1, r1], [l2, r2] (l1l2r1r2)[l_1,~r_1],~[l_2,~r_2]~(l_1 \le l_2 \le r_1 \le r_2),显然有 f((l1, r2))=f((l1, r1))f((l2, r2))f\big((l_1,~r_2)\big) = f\big((l_1,~r_1)\big) \bigcup f\big((l_2,~r_2)\big)。而我们通过上面的结论可知等号右侧的两个区间有交,可以通过对左端点取较小值,右端点取较大值的方法得到他们的并。

        这启发我们得到:f((l, r))=i=lr1f((i, i+1))f\big((l,~r)\big) = \bigcup_{i = l}^{r - 1} f\big((i,~i + 1)\big)。若预处理得到 f((i, i+1))=(xi, yi)f\big((i,~i + 1)\big) = (x_i,~y_i),则 f((l, r))=(mini=lr1xi,maxi=lr1yi)f\big((l,~r)\big) = (\min_{i = l}^{r - 1} x_i, \max_{i = l}^{r - 1} y_i),可通过两个 ST 表做到 O(1)O(1) 得出答案。

        考虑当我们需要进行多次 ff 操作时需要如何计算,由于 fa+b((l, r))=fa(fb((l, r)))f^{a + b}\big((l,~r)\big) = f^a\Big(f^b\big((l,~r)\big)\Big),不难想到使用倍增的思想,对于每个 kk 我们预处理 f2k((i, i+1))f^{2^k}\big((i,~i + 1)\big),再使用与上面相同的 ST 表维护方法即可 O(1)O(1) 算出 f2k((l, r))f^{2^k}\big((l,~r)\big)

        询问 (l, r)(l,~r) 最少需操作多少次时,我们只需要从大往小枚举 kk 找到最大的 xx 满足 fx((l, r))(1, n)f^x\big((l,~r)\big) \neq (1,~n),除去无解情况后答案即为 x+1x + 1

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

        Code

        偷了个懒使用线段树实现。复杂度 O((n+q)log2n)O((n + q) \log^2 n),也可通过本题。

        View on GitHub

        /**
         * @file 1707E.cpp
         * @author Macesuted (i@macesuted.moe)
         * @date 2022-07-17
         *
         * @copyright Copyright (c) 2022
         *
         */
        
        #include <bits/stdc++.h>
        using namespace std;
        
        #ifndef LOCAL
        #define endl '\n'
        #endif
        
        bool mem1;
        
        #define maxn 100005
        #define maxlgn 18
        
        typedef pair<int, int> pii;
        
        pii merge(const pii& a, const pii& b) { return {min(a.first, b.first), max(a.second, b.second)}; }
        
        class SegmentTree {
           private:
            pii tree[maxn << 2];
            int n;
        
            void pushUp(int p) { return tree[p] = merge(tree[p << 1], tree[p << 1 | 1]), void(); }
            void insert(int p, int l, int r, int qp, pii v) {
                if (l == r) return tree[p] = v, void();
                int mid = (l + r) >> 1;
                qp <= mid ? insert(p << 1, l, mid, qp, v) : insert(p << 1 | 1, mid + 1, r, qp, v);
                return pushUp(p);
            }
            pii query(int p, int l, int r, int ql, int qr) {
                if (ql <= l && r <= qr) return tree[p];
                int mid = (l + r) >> 1;
                if (qr <= mid) return query(p << 1, l, mid, ql, qr);
                if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr);
                return merge(query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr));
            }
        
           public:
            void resize(int _n) { return n = _n, void(); }
            void insert(int p, pii v) { return insert(1, 1, n, p, v); }
            pii query(pii a) { return a.first >= a.second ? pii{INT_MAX, INT_MIN} : query(1, 1, n, a.first, a.second - 1); }
        };
        
        int a[maxn];
        SegmentTree ST[maxlgn];
        
        void solve(void) {
            int n, q;
            cin >> n >> q;
            for (int i = 1; i <= n; i++) cin >> a[i];
            for (int i = 0; i < maxlgn; i++) ST[i].resize(n);
            for (int i = 1; i < n; i++) ST[0].insert(i, {min(a[i], a[i + 1]), max(a[i], a[i + 1])});
            for (int i = 1; i < maxlgn; i++)
                for (int j = 1; j < n; j++) ST[i].insert(j, ST[i - 1].query(ST[i - 1].query({j, j + 1})));
            while (q--) {
                int l, r;
                cin >> l >> r;
                if (l == 1 && r == n)
                    cout << 0 << endl;
                else if (l == r)
                    cout << -1 << endl;
                else {
                    int ans = 0;
                    for (int i = maxlgn - 1; ~i; i--) {
                        pii ret = ST[i].query({l, r});
                        if (ret != pii{1, n}) ans |= 1 << i, tie(l, r) = ret;
                    }
                    ans++;
                    cout << (ans == (1 << maxlgn) ? -1 : ans) << endl;
                }
            }
            return;
        }
        
        bool mem2;
        
        int main() {
            ios::sync_with_stdio(false), cin.tie(nullptr);
        #ifdef LOCAL
            cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
        #endif
        
            int _ = 1;
            while (_--) solve();
        
        #ifdef LOCAL
            cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
        #endif
            return 0;
        }
        
        👍 7
        ❤️ 3
        🕊️ 3
        👀 2
        😄 1
        🍋 1
      • @ 2022-7-19 7:47:15

        #038.2022.7.19

        Luogu P3911 最小公倍数之和

        标签:莫比乌斯反演,数论

        Statement

        给定 NN 个数 A1,A2,,ANA_1,A_2,\cdots,A_N,求 i=1Nj=1Nlcm(Ai,Aj)\sum_{i=1}^N\sum_{j=1}^N \mathrm{lcm}(A_i,A_j) 的值。

        Data Range :1N5×104\textbf{Data Range :} 1 \le N \le 5\times 10^41Ai5×1041 \le A_i \le 5\times 10^4

        Solution

        solution

        肯定还是要考虑莫反,但是题目中给定了 AiA_i,这就不能常规的进行反演。

        但是其实没有影响的,我们记录每个数 xx 的出现次数 cxc_x,然后原式子等价于下面的式子:

        i=1Nj=1Nlcm(i,j)×ci×cj\sum_{i=1}^N\sum_{j=1}^N \text{lcm}(i,j) \times c_i \times c_j

        于是可以进行反演了。

        i=1Nj=1Nlcm(i,j)×ci×cj\sum_{i=1}^N\sum_{j=1}^N \text{lcm}(i,j) \times c_i \times c_j

        i=1Nj=1Ni×jgcd(i,j)×ci×cj\sum_{i=1}^N\sum_{j=1}^N \dfrac{i \times j}{\gcd(i,j)} \times c_i \times c_j

        然后我们套路的改为枚举 gcd\gcd

        d=1Ni=1Ndj=1Ndid×jdd×cid×cjd[(i,j)=1]\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \dfrac{id \times jd}{d} \times c_{id} \times c_{jd} [(i,j)= 1]

        d=1Ni=1Ndj=1Ndijd×cid×cjd[(i,j)=1]\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} ijd \times c_{id} \times c_{jd} [(i,j)= 1]

        d=1Ni=1Ndj=1Ndx(i,j)μ(x)×ijd×cid×cjd\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \sum_{x|(i,j)} \mu(x) \times ijd \times c_{id} \times c_{jd}

        d=1Ni=1Ndj=1Ndxi,xjμ(x)×ijd×cid×cjd\sum_{d=1}^N \sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{N}{d}} \sum_{x|i,x | j} \mu(x) \times ijd \times c_{id} \times c_{jd}

        之后枚举 xx

        d=1Nx=1Ndμ(x)i=1Ndxj=1Ndxix×jx×d×cidx×cjdx\sum_{d=1}^N \sum_{x=1}^{\frac{N}{d}}\mu(x) \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ix \times jx \times d \times c_{idx} \times c_{jdx}

        d=1Nx=1Ndμ(x)x2i=1Ndxj=1Ndxijd×cidx×cjdx\sum_{d=1}^N \sum_{x=1}^{\frac{N}{d}}\mu(x) x^2 \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ijd\times c_{idx} \times c_{jdx}

        d=1Ndx=1Ndμ(x)x2i=1Ndxj=1Ndxij×cidx×cjdx\sum_{d=1}^N d\sum_{x=1}^{\frac{N}{d}}\mu(x) x^2 \sum_{i=1}^{\frac{N}{dx}} \sum_{j=1}^{\frac{N}{dx}} ij\times c_{idx} \times c_{jdx}

        T=xdT = xd,代入进行化简。

        T=1NdTd×μ(Td)×(Td)2i=1NTj=1NTij×cidTd×cjdTd\sum_{T=1}^N \sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2 \sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}}

        T=1N(dTd×μ(Td)×(Td)2)×(i=1NTj=1NTij×cidTd×cjdTd)\sum_{T=1}^N (\sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2) \times (\sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}})

        对于 dTd×μ(Td)×(Td)2\sum_{d|T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2 这一部分,他等价于 TdT×μ(Td)×(Td)T \sum_{d|T} \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d}),于是我们可以在进行线性筛之后暴力枚举倍数预处理就好了,复杂度是对的。

        所以我们只用考虑后面一部分怎么做,也就是 i=1NTj=1NTij×cidTd×cjdTd\sum_{i=1}^{\frac{N}{T}} \sum_{j=1}^{\frac{N}{T}} ij \times c_{\frac{idT}{d}} \times c_{\frac{jdT}{d}}

        我们发现这东西其实不用写成 ijij 两层循环,完全可以写成 (i=1NTi×cidTd)2=(i=1NTi×ciT)2(\sum_{i=1}^{\frac{N}{T}} i \times c_{\frac{idT}{d}})^2 = (\sum_{i=1}^{\frac{N}{T}} i \times c_{iT})^2

        和上面一样的,莫反题到最后优化也就是整除分块和预处理了。

        我们对每个 TT 暴力预处理 i=1NTi×ciT\sum_{i=1}^{\frac{N}{T}} i \times c_{iT},根据经典结论 i=1NNi=nlnn\sum_{i=1}^N \dfrac{N}{i} = n \ln n

        然后枚举倍数的复杂度也是这样的,所以之前的预处理复杂度也是 nlnnn\ln n 的。

        于是总预处理复杂度为 nlnnn \ln n

        最后我们直接暴力回答答案就好了,统计答案的复杂度为 O(n)O(n)

        // 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
        // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱!
        // 没有力量的理想是戏言,没有理想的力量是空虚
        #include <bits/stdc++.h>
        #define LL long long
        #define int long long
        using namespace std;
        char ibuf[1 << 15], *p1, *p2;
        #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++)
        inline int read() {
          char ch = getchar();  int x = 0, f = 1;
          while (ch < '0' || ch > '9')  {  if (ch == '-')  f = -1;  ch = getchar();  }
          while (ch >= '0' && ch <= '9')  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
          return x * f;
        }
        void print(LL x) {
          if (x > 9)  print(x / 10);
          putchar(x % 10 + '0');
        }
        template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
        template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
        #define rep(i, l, r) for (int i = (l); i <= (r); i++)
        #define repd(i, l, r) for (int i = (l); i >= (r); i--)
        #define REP(i, l, r)  for (int i = (l); i < (r); i++)
        const int N = 5e4 + 6, M = 5e4 + 5;
        int n, vis[N], c[N], pr[N], tot, mu[N];
        void prime(int n) {
          mu[1] = 1;
          rep (i, 2, n) {
            if (!vis[i]) {  pr[++tot] = i;  mu[i] = -1;  }
            rep (j, 1, tot) {
              if (pr[j] * i > n)  break;
              vis[i * pr[j]] = 1;
              if (i % pr[j] == 0) {
                mu[i * pr[j]] = 0;  break;
              }  else {
                mu[i * pr[j]] = -mu[i];
              }
            }
          }
        }
        int f[N], g[N];
        void solve() {
          n = read();
          rep (i, 1, n) {  int x = read();  c[x] ++;  }
          prime(M);
          rep (i, 1, M) 
            for (int j = i; j <= M; j += i)  f[j] += mu[i] * i;
          rep (i, 1, M)  f[i] *= i;
          rep (T, 1, M)
            for (int i = 1; i <= M / T; i++)  g[T] += i * c[i * T];
          int ans = 0;
          rep (T, 1, M)  ans += f[T] * g[T] * g[T];
          cout << ans;
        }
        signed main () {
        #ifdef LOCAL_DEFINE
          freopen("1.in", "r", stdin);
          freopen("1.ans", "w", stdout);
        #endif
          int T = 1;  while (T--)  solve();
        #ifdef LOCAL_DEFINE
          cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
        #endif
          return 0;
        }
        
        ❤️ 5
        👍 4
        • @ 2022-7-14 8:02:10

          #037 2022.7.13

          CF708E Student's Camp

          标签:dp,math,*3100

          Statement

          有一个 (n+2)×m(n + 2) \times m 的网格,初始是全部联通的。

          除了第一行与最后一行的网格,每天每一行的最左边和最右边的格子都有 pp 的概率消失。

          消失的网格不再联通,求 kk 天后,网格始终保持联通的概率。

          答案对 109+710^9 + 7 取模。

          Data Range:1n,m1.5×103,k105\textbf{Data Range:} 1 \leq n,m \leq 1.5 \times 10^3, k\leq 10^5

          Solution

          Solution

          不难发现最后每一行剩下的一定都会是一个连续的区间,而且每行之间相互独立。

          自然设立状态 dpi,l,rdp_{i,l,r} 表示当前是第 ii 行,kk 天后这一行剩下的区间为 [l,r][l, r],第 00 行到第 ii 行都联通的概率。

          先考虑算变成区间 [l,r][l,r] 的概率。

          kk 天内,消失 ii 个格子的概率为 gi=(ki)pi×(1p)kig_i = \binom{k}{i} p^i \times (1-p)^{k-i}

          所以剩下区间 [l,r][l,r] 的概率为 gl1×gmrg_{l-1} \times g_{m-r}

          当然还需要检查这段区间长度是否合法,因为最多消失 2k2k 个格子。

          转移式子不难写出。

          dpi,l,r=gl1×gmr[l1,r1][l,r]dpi1,l1,r1dp_{i,l,r} = g_{l-1} \times g_{m-r} \sum_{[l_1, r_1] \cap [l,r] \neq \varnothing} dp_{i-1,l_1,r_1}

          复杂度 nm4nm^4,显然不行,而且状态数都为 nm2nm^2

          那考虑优化状态,去掉左端点的限制。

          dpi,rdp_{i,r} 表示第 ii 行的剩余区间的右端点为 rr,第 00 行到第 ii 行都联通的概率,转移的时候枚举 ll 进行转移。

          考虑一个和区间 [l,r][l,r] 有交的区间 [l1,r1][l_1,r_1]

          它满足 r1l,l1rr_1 \geq l, l_1 \leq r,那么容斥把这一部分算出来即可。

          对于 r1<lr_1 < l 的部分,枚举 ll 时计算 j=1l1dpi1,j\sum_{j=1}^{l-1} dp_{i-1,j}

          对于 l1>rl_1 > r 的部分,因为网格是对称的,所以 fi,rf_{i,r} 也可以表示左端点为 mr+1m-r+1 且联通的概率,因此这一部分可以计算为 j=1mrfi1,j\sum_{j=1}^{m-r} f_{i-1,j}

          于是转移如下。

          dpi,r=l=1rgl1gmr(j=1mfi1,jj=1i1fi1,jj=1mrfi1,j)dp_{i,r} = \sum_{l=1}^r g_{l-1} g_{m-r} (\sum_{j=1}^m f_{i-1, j} - \sum_{j = 1}^ {i-1} f_{i-1,j} - \sum_{j=1}^{m-r} f_{i-1,j})

          这东西长得就很一脸前缀和的样子,那就考虑前缀和优化。

          sjs_{j} 表示 k=1jfi1,k\sum_{k=1}^j f_{i-1,k}

          fi,r=gmrl=1rgl1)(smsl1smr)f_{i,r} = g_{m-r} \sum_{l=1}^r g_{l-1} )(s_m - s_{l-1} - s_{m-r})

          fi,r=gmr×((smsmr)l=1rgl1l=1rgl1sl1)f_{i,r} = g_{m-r} \times( (s_m - s_{m-r}) \sum_{l = 1}^r g_{l-1} - \sum_{l=1}^r g_{l-1} s_{l-1})

          在令 pip_iqiq_i 依次为 gig_igi×sig_i \times s_i 的前缀和,之后即可做到 O(1)O(1) 转移,总时间复杂度 o(nm)o(nm)

          // 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
          // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱!
          #include <bits/stdc++.h>
          #define int long long
          using namespace std;
          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 = 3e6, mod = 1e9 + 7;
          int n, m, a, b, pt, pt2, k, ans, fac[N], ifac[N], dp[3005][3005], g[3005];
          int power(int a,int b) { int ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1;} return ans; }
          int binom(int n,int m) { return fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
          int s[N], p[N], q[N];
          signed main () {
            n = read(), m = read(), a = read(), b = read(), k = read(); 
            fac[0] = 1; for (int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i % mod;
            ifac[k] = power(fac[k], mod - 2); for (int i = k - 1; ~i; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
            pt = a * power(b, mod - 2) % mod; pt2 = 1 - pt; pt2 += mod; pt2 %= mod;
            for (int i = 0; i <= k && i <= m; i++) g[i] = binom(k, i) * power(pt, i) % mod * power(pt2, k - i) % mod;
            dp[0][m] = 1;  p[0] = g[0]; 
            for (int i = 1; i <= m; i++) p[i] = p[i - 1] + g[i], p[i] %= mod;
            for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= m; j++) s[j] = s[j - 1] + dp[i - 1][j], s[j] %= mod;
              for (int j = 1; j <= m; j++) q[j] = q[j - 1] + g[j] * s[j] % mod, q[j] %= mod;
              for (int r = 1; r <= m; r++) dp[i][r] = g[m - r] * ( (s[m] - s[m - r] + mod) % mod * p[r - 1] % mod - q[r - 1] + mod) % mod;
            }  
            for (int i = 1; i <= m; i++) { ans += dp[n][i]; ans %= mod;}
            printf("%lld\n", ans);
            return 0;
          }
          
          👍 6
          ❤️ 5
          😄 3
          • @ 2022-7-9 12:57:38

            #036 2022.7.9 [IOI2020] mushrooms

            标签:构造,交互。

            (不要提交到洛谷上的这道题,那道题交不了) 研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。

            作为研究的一部分,安德鲁采集了 nn 个蘑菇,编号为 00n1n−1。每个蘑菇均为两种蘑菇种类之一,称为 AABB

            安德鲁知道蘑菇 00 属于种类 AA ,但是由于这两种蘑菇看起来很相似,他不知道蘑菇 11n1n−1 属于哪一种。

            幸运的是,安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时,需要将两个或者多个蘑菇放到机器里,并摆成一排(以任意顺序),然后打开机器。接下来,这台机器会计算所有不属于同一种类的相邻蘑菇对的个数。例如,如果你把种类为 [A,B,B,A][A,B,B,A] 的蘑菇(按照这个顺序)放到机器中,结果应该是 22

            但是,因为机器操作非常昂贵,机器只能使用有限的次数。此外,在机器的所有使用中,放置到机器中的蘑菇总数不能超过 100000100000。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 AA 的蘑菇。

            题解

            为了方便, 以下我们将不加申明的将 retret 用作上一次 query\texttt{query} 操作的返回值, 读者可以根据上下文知道这个 retret 的值.

            Method 1

            我们考虑朴素暴力: 对所有 i[1,n1]i\in [1, n-1] 执行操作 query({0,i})\texttt{query}(\{0, i\}), 这是一个时间复杂度 O(n)O(n) 的算法, 可以获得 ... 10 分.

            Method 2

            我们发现: 如果已知有 kk 个 0, 分别是 af1,af2,afka_{f_1}, a_{f_2}, \cdots a_{f_k}, 那么可以执行这样的一次操作来求出长度为 kk 的序列 g1,g2,gkg_1, g_2, \cdots g_k 中 0 的个数: query({g1,f1,g2,f2,gk,fk})\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\}). 容易知道 i=1kgi=ret2\sum\limits_{i=1}^k g_i = \lceil\frac{ret}{2}\rceil. 有 kk 个 1 的情况下同理.

            而如何求出 f1,f2,fkf_1, f_2, \cdots f_k 呢? 显然直接套用 Method 1 即可. 我们使用类似根号分治的思想可以做到 O(n)O(\sqrt n) 的复杂度(实际上后续都是常数优化, 并没有超越这个复杂度.)

            Optimize 1

            我们考察这种操作: query({g1,f1,g2,f2,gk,fk})\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\}). 那么可以根据 retret 的奇偶性判断 g1g_1 的值, 具体来说, 由于 g2,g3,gkg_2, g_3, \cdots g_{k} 左右均为相同的值, 故不管这些数如何取值, 均不会影响 retret 的奇偶性, 所以 retret 的奇偶性只由 ag1,af1a_{g_1}, a_{f_1} 决定, 也即可以得出 ag1a_{g_1} 的具体值. 于是我们可以动态的维护当前 0/1 的个数和这些 0/1 的位置然后每次启发式的用 0/1 去询问.

            以上优化的代码

            Optimize 2

            这同时也可以对 Method 1 的过程做出优化: 在有两个相同值的数 ax,aya_x, a_y 时, 每次可以通过 query{p, x, q, y}\texttt{query\{p, x, q, y\}} 确定 apa_p, aqa_q 的具体值.

            Optimize 3

            Method 2 的过程已经难以优化, 接下来我们来优化 Method 1 的过程.

            不妨考虑我们有充分多的 0 和充分多的 1, 接下来我们考虑如何更优的询问, 具体来说, 我们将用 2 询问次得到 5 个数的具体值.

            我们设 pip_i 为所有 0 的位置序列, qiq_i 为所有 1 的位置序列. 即 必有 api=0,aqi=1a_{p_i}=0, a_{q_i}=1.

            我们先进行询问 query({x,p1,y,p2,z,p3})\texttt{query}(\{x, p_1, y, p_2, z, p_3\}). 根据返回值讨论: 首先可以发现根据 retret 的奇偶性确定 axa_x, 然后我们令 retret2ret\leftarrow \lfloor\frac{ret}{2}\rfloor, 这样就有 ay+az=reta_{y}+a_{z} = ret. 显然只需要考虑 ret=1ret = 1 的情况.

            如果 ret=1ret = 1, 我们接下来进行询问 query({q1,y,q2,p1,z,p2,u,p3,v})\texttt{query}(\{q_1, y, q_2, p_1, z, p_2, u, p_3, v\}), 然后令 retret1ret\leftarrow ret-1(这是因为有相邻的 q2,p1q_2, p_1).

            首先考察 retret 的奇偶性以确定 vv, 然后令 retret2ret\leftarrow \lfloor \frac{ret}{2}\rfloor, 这样就有 1ay+az+au=ret1-a_y+a_z+a_u = ret, 也即 2az+au=ret2a_z+a_u = ret, 这样又可以根据 retret 的奇偶性来确定 aua_u, 从而确定 aza_zaya_y.

            以上优化的代码

            Optimize 4

            调整你的参数.

            AC 代码

            👍 6
            ❤️ 3
          • @ 2022-7-8 0:06:12

            #035 2022.7.8

            【YsOI2020】造林

            标签:Hash。

            给定一个树,定义一个节点的权值为删去这个节点后的图中最大连通块的大小。定义树的品种为所有节点权值构成的可重集,两树品种相同当且仅当可重集相同。

            现在要给这个树加一个叶子,求能得到多少品种的树,以及每个品种有多少种添加方法得到。

            n2×106n\leq2\times10^6,时限 4s。

            题解

            显然,对于一个不是重心的节点,删掉这个点后的连通块里面,最大的连通块就是包含重心的连通块。因此如果叶子添加在重心头上,别的点权值都要加一,重心不变。(对于两个重心的情况,在一个重心上加点时,显然另一个重心权值是要加一的。)

            考虑如果不加在重心上。注意到上面提到的性质,哪些节点的权值会改变(如图 1,3 号节点是重心,把它当作根):

            图 1

            假设我们向 9 号节点添加一个叶子,来分类讨论。

            1. 和被添加叶子的点不在同一子树(如 1,2,6,7 号点),显然权值都会加一。
            2. 和被添加叶子点在同一侧,不在这个点到根的路径上(如 5,10 号点),考虑到删掉后其最大连通块是根的那一侧,因此权值也会加一。
            3. 重心(如 3 号点),若被添加叶子点在重心的最大子树内,则重心权值加一;否则不变。
            4. 被添加叶子节点本身(如 9 号点),显然不变。
            5. 重心和被添加叶子点路径上的点(如 4 号点),因为删掉它后新叶子没有连通到根,所以不变。

            总结一下,如果新叶子在重心的最大子树内,不会改变的就是重心到它的链(不包括两端);否则,不会改变的是重心到它的链(包括重心,不包括被添加节点)。

            我们要维护的是所有点贡献的集合,考虑从重心出发深搜整颗树,到达一个点时,只需要修改这一个点的贡献即可。可以用 Hash 实现。

            注意到集合是无序的,如果和我考场降智 naive 地用每个点权值的 kk 次方和(kk 为常量)当 Hash 函数,注意到 ak+bk=cka^k + b^k = c^kklogmax(a,b,c)k\leq\log\max(a,b,c) 时分布不少,很大概率被卡掉。因此考虑维护每个点权值构成的桶,对这个桶进行字符串 Hash 即可。

            单 Hash 也被卡了(我运气背还是出题人毒瘤还是生日悖论再现都有可能),建议双 Hash。

            剩下的都是一些细节问题,例如两个重心的情况,可以考虑断掉中间的边,拆成两棵树考虑(在一棵树上时反正另一棵树点的贡献都是要加一的),等等。

            代码
            #include<bits/stdc++.h>
            #define int long long
            using namespace std;
            bool Begin;
            const int max_n=2000006,mod1=1000000009,mod2=998244853;
            inline int read(){
                int x=0;bool w=0;char c=getchar();
                while(c<'0' || c>'9') w|=c=='-',c=getchar();
                while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
                return w?-x:x;
            }
            inline void write(int x){
                if(x<0) putchar('-'),x=-x;
                if(x>9) write(x/10);
                putchar(x%10^48);
            }
            struct graph{
                int ct,hd[max_n],to[max_n<<1],nx[max_n<<1];
                graph(){ct=1;}
                inline void add(int u,int v){
                    nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
                }
            }e;
            inline int MOD1(int x){
                return (x>=mod1?x-mod1:x);
            }
            inline int MOD2(int x){
                return (x>=mod2?x-mod2:x);
            }
            struct Hashnum{
                int x1,x2;
                Hashnum(int A=0,int B=0):x1(A),x2(B){}
                bool operator == (const Hashnum &b) const{
                    Hashnum a=*this;
                    return (a.x1==b.x1 && a.x2==b.x2);
                }
                bool operator < (const Hashnum &b) const{
                    Hashnum a=*this;
                    return (a.x1<b.x1 || (a.x1==b.x1 && a.x2<b.x2));
                }
                Hashnum operator * (const Hashnum &b) const{
                    Hashnum a=*this;
                    return Hashnum(a.x1*b.x1%mod1,a.x2*b.x2%mod2);
                }
                Hashnum operator + (const Hashnum &b) const{
                    Hashnum a=*this;
                    return Hashnum(MOD1(a.x1+b.x1),MOD2(a.x2+b.x2));
                }
                Hashnum operator - (const Hashnum &b) const{
                    Hashnum a=*this;
                    return Hashnum(MOD1(a.x1-b.x1+mod1),MOD2(a.x2-b.x2+mod2));
                }
                Hashnum operator * (const int &b) const{
                    Hashnum a=*this;
                    return a*Hashnum(b,b);
                }
                Hashnum operator + (const int &b) const{
                    Hashnum a=*this;
                    return a+Hashnum(b,b);
                }
                Hashnum operator - (const int &b) const{
                    Hashnum a=*this;
                    return a-Hashnum(b,b);
                }
            }hs;
            
            int n,sz[max_n],mxs[max_n];
            
            inline void dfs1(int u,int fa){
                sz[u]=1;
                for(register int i=e.hd[u];i;i=e.nx[i]){
                    int v=e.to[i];
                    if(v==fa) continue;
                    dfs1(v,u);
                    sz[u]+=sz[v];
                    mxs[u]=max(mxs[u],sz[v]);
                }
                mxs[u]=max(mxs[u],n-sz[u]);
            }
            int zx,zx2;
            inline void dfs2(int u,int fa){
                zx=u;
                for(register int i=e.hd[u];i;i=e.nx[i]){
                    int v=e.to[i];
                    if(v==fa) continue;
                    if(sz[v]>n/2)
                        dfs2(v,u);
                }
            }
            
            int ans[max_n],tong[max_n],pw1[max_n],pw2[max_n];
            
            int B1=114514,B2=11037;
            
            map<Hashnum,int> mp;
            inline void dfs3(int u,int fa,Hashnum hs){
                for(register int i=e.hd[u];i;i=e.nx[i]){
                    int v=e.to[i];
                    if(v==fa || v==zx || v==zx2) continue;
                    Hashnum t=hs-Hashnum(pw1[mxs[v]+1],pw2[mxs[v]+1])+Hashnum(pw1[mxs[v]],pw2[mxs[v]]);
                    ++mp[t];
                    dfs3(v,u,t);
                }
            }
            
            bool End;
            #define File "forest"
            signed main(){
                // #ifndef ONLINE_JUDGE
                // freopen(File ".in","r",stdin);
                // freopen(File ".out","w",stdout);
                // #endif
                // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
                n=read();
                for(register int i=1;i<n;++i){
                    int u=read(),v=read();
                    e.add(u,v),e.add(v,u);
                }
                dfs1(1,-1);
                dfs2(1,-1);
                for(register int i=1;i<=n;++i)
                    ++tong[mxs[i]+1];
                ++tong[n];
                if(!(n&1)) for(register int i=1;i<=n;++i)
                    if(i!=zx && mxs[i]==mxs[zx]){
                        zx2=i;
                        break;
                    }
                for(register int i=1;i<=n;++i){
                    hs.x1=(hs.x1*B1+tong[i]),
                    hs.x2=(hs.x2*B2+tong[i]);
                }
                pw1[n]=pw2[n]=1;
                for(register int i=n-1;i;--i){
                    pw1[i]=pw1[i+1]*B1%mod1,
                    pw2[i]=pw2[i+1]*B2%mod2;
                }
                ++mp[hs-Hashnum(pw1[mxs[zx]+1],pw2[mxs[zx]+1])+Hashnum(pw1[mxs[zx]],pw2[mxs[zx]])];
                if(zx2) ++mp[hs-Hashnum(pw1[mxs[zx2]+1],pw2[mxs[zx2]+1])+Hashnum(pw1[mxs[zx2]],pw2[mxs[zx2]])];
                dfs3(zx,-1,hs);
                if(zx2) dfs3(zx2,-1,hs);
                int cnt=0;
                for(auto i=mp.begin();i!=mp.end();++i)
                    ans[++cnt]=(*i).second;
                sort(ans+1,ans+1+cnt);
                write(cnt),putchar('\n');
                for(register int i=1;i<=cnt;++i)
                    write(ans[i]),putchar('\n');
                return 0;
            }
            
            👍 5
            • @ 2022-7-7 10:43:22

              #034 2022.7.7

              标签:网络流。

              Statement

              nn 个酿酒点和 mm 个存酒点。对于第 ii 个酿酒点,生产 xxxx 为实数)升酒需要花费 ai×x2+bi×xa_i \times x^2 + b_i \times x,最多能生产 cic_i 升酒。对于第 ii 个存酒点,其最多能存储 did_i 升酒。每个酿酒点生产酒后需立即运至该酿酒点可到达的存酒点,每个酿酒点可到达的存酒点已知并给出。求:1. 所有酿酒点最大一共能产生多少酒 2. 在酿酒量达到最大值时花费的最小值为多少,以分数形式给出。

              n,m100, 0ai,bi,ci,di3n, m \le 100,~0 \le a_i,b_i,c_i,d_i \le 3

              Solution

              Solution

              第一问建图后直接最大流即可得出。

              酿酒代价为二次函数不易于计算,一个自然的想法是将这个二次函数从定义域上切割为若干段,将每一段内的部分近似为一个一次函数,然后就可以对于每一段建立一条对应的边,跑费用流即可。由于此处二次函数斜率递增,定义域靠前的段在代价上优于靠后的段,因此不需要考虑取这些段的先后顺序而可能带来的不合法取法。

              但是此题要求输出分数,也就是不允许误差的存在。我们发现上面的做法分的段数越多,结果误差就越小,当每一段的长度无线接近于零,段数接近正无穷时误差即可消除。此时每一段内的一次函数就成为了该二次函数的导数:2aix+bi2 a_i x + b_i

              虽然解决了误差问题,但是段数达到了正无穷,我们无法直接对于每一段建边跑费用流。但是我们发现,若假设存酒点容量无穷,即只考虑产酒点总产量而不考虑存酒点限制的情况下,所有的最优方案一定是这样的:存在一个实数 ll 作为阈值,每一个产酒点对应的花费二次函数上导数小于 ll 的部分对应的定义域大小即为该产酒点产量。贪心策略下显然成立。

              因此我们考虑构建函数 F(x)F(x) 表示当阈值为 xx 时,不考虑存酒点限制情况下的产酒点总产量。若令 Fi(x)F_i(x) 表示阈值为 xx 时第 ii 个产酒点的产量,可以发现 Fi(x)=12aixbi2ai(x[bi, 2aici+bi])F_i(x) = \frac 1 {2a_i} x - \frac {b_i} {2a_i} (x \in [b_i,~2 a_i c_i + b_i])。而 F(x)=iFi(x)F(x) = \sum_i F_i(x),所以 F(x)F(x) 应当由 O(n)O(n) 个一次函数首尾相连形成。

              该阈值与费用流 SPFA 跑出的 dist[T]dist[T] 功能类似,若要模拟费用流过程,我们可以令阈值从 00 开始不断增长,每次更改阈值后重新通过 Fi(x)F_i(x) 计算每条边的对应流量。费用流过程中还可将存酒点的流量限制加入,从而算出考虑存酒点限制情况下的总产量。

              由于不允许存在精度误差因此我们无法做到真正模拟该过程,但是通过这个思路我们发现在阈值不断增加的过程中,存酒点总是先尽可能多地存酒,直至其容量达到上限后对部分酿酒点的产量产生限制。也就是说,我们可以通过 F(x)F(x) 结合网络流得到 G(x)G(x) 表示考虑存酒点容量限制的情况下,阈值为 xx 时的总产量。G(x)G(x) 只会在 F(x)F(x) 的基础上多 O(m)O(m) 个端点,其图像由 O(n+m)O(n + m) 个一次函数首尾相连形成。

              但是 G(x)G(x) 不像 F(x)F(x) 可以直接通过计算得出,G(x)G(x) 的每一个点都需要网络流计算得出。不过我们发现 G(x)G(x) 的大部分图像呈现上凸壳的形态,我们可以在定义域上分治得到整个图像:令 solve(l, r)solve(l,~r) 过程查找横坐标在 (l, r)(l,~r) 间的所有端点位置,我们在 llrr 上分别用网络流算出坐标,并结合残量网络算出斜率,可得两个端点处的一次函数。取这两个一次函数的交点,令其为 midmid,计算 midmid 处的一次函数,若与两端的一次函数相同则说明 (l, r)(l,~r) 范围内已再无端点,否则向 (l, mid)(l,~mid)(mid, r)(mid,~r) 递归求解。但是注意到 aia_i 可能等于零,也就是说一些一次函数可能出现斜率无穷的情况,因此需要在 x=0, 1, 2, 3x = 0,~1,~2,~3 处强制断开,在 (0, 1), (1, 2), (2, 3), (3, +)(0,~1),~(1,~2),~(2,~3),~(3,~+\infty) 段分开分治求解。

              计算出 G(x)G(x) 的图像后,通过计算其积分即可得到最终答案。

              Code

              View on GitHub

              /**
               * @file 2138.cpp
               * @author Macesuted (i@macesuted.moe)
               * @date 2022-07-05
               *
               * @copyright Copyright (c) 2022
               *
               */
              
              #include <bits/stdc++.h>
              using namespace std;
              
              #ifndef LOCAL
              #define endl '\n'
              #endif
              
              bool mem1;
              
              #define maxn 105
              #define eps 1e-9
              #define feps 1e-11
              
              bool con[maxn][maxn];
              int n, m, a[maxn], b[maxn], c[maxn], d[maxn];
              
              class Frac {
                 private:
                  int64_t x, y;
              
                  int64_t gcd(int64_t a, int64_t b) { return b ? gcd(b, a % b) : a; }
              
                 public:
                  Frac(int64_t x_ = 0, int64_t y_ = 1) {
                      int64_t g = gcd(x_, y_);
                      x = x_ / g, y = y_ / g;
                  }
                  operator double() { return (double)x / y; }
                  operator int64_t() { return x / y; }
                  Frac operator+(const Frac& o) const { return Frac(x * o.y + y * o.x, y * o.y); }
                  Frac operator-(const Frac& o) const { return Frac(x * o.y - y * o.x, y * o.y); }
                  Frac operator*(const Frac& o) const { return Frac(x * o.x, y * o.y); }
                  Frac operator/(const Frac& o) const { return Frac(x * o.y, y * o.x); }
                  bool operator==(const Frac& o) const { return x == o.x && y == o.y; }
                  Frac& operator+=(const Frac& o) { return *this = *this + o; }
                  Frac& operator-=(const Frac& o) { return *this = *this - o; }
                  Frac& operator*=(const Frac& o) { return *this = *this * o; }
                  Frac& operator/=(const Frac& o) { return *this = *this / o; }
                  void print(void) {
                      if (y < 0) x = -x, y = -x;
                      return cout << x << '/' << y, void();
                  }
              };
              
              typedef pair<Frac, Frac> pff;
              
              class Dinic {
                 private:
                  struct Edge {
                      int to, rev;
                      double cap;
                  };
              
                  vector<vector<Edge>> graph;
                  vector<vector<Edge>::iterator> cur;
                  vector<int> dist;
                  queue<int> que;
              
                  bool bfs(void) {
                      for (int i = 1; i <= n + m + 2; i++) dist[i] = -1, cur[i] = graph[i].begin();
                      que.push(n + m + 1), dist[n + m + 1] = 0;
                      while (!que.empty()) {
                          int p = que.front();
                          que.pop();
                          for (auto i : graph[p])
                              if (i.cap > feps && !~dist[i.to]) dist[i.to] = dist[p] + 1, que.push(i.to);
                      }
                      return ~dist[n + m + 2];
                  }
                  double dfs(int p, double rest) {
                      if (rest < feps || p == n + m + 2) return rest;
                      double use = 0, c;
                      for (auto i = cur[p]; i != graph[p].end() && rest > feps; i++) {
                          cur[p] = i;
                          if (dist[p] + 1 != dist[i->to] || i->cap < feps) continue;
                          if ((c = dfs(i->to, min(rest, i->cap))) < feps) dist[i->to] = -1;
                          i->cap -= c, graph[i->to][i->rev].cap += c, use += c, rest -= c;
                      }
                      return use;
                  }
              
                 public:
                  void addEdge(int from, int to, double cap) {
                      return graph[from].push_back(Edge{to, (int)graph[to].size(), cap}),
                             graph[to].push_back(Edge{from, (int)graph[from].size() - 1, 0});
                  }
                  pff dinic(double lim) {
                      graph.clear(), graph.resize(n + m + 3), cur.resize(n + m + 3), dist.resize(n + m + 3);
                      for (int i = 1; i <= n; i++)
                          if (a[i] == 0) {
                              if (b[i] < lim) addEdge(n + m + 1, i, c[i]);
                          } else
                              addEdge(n + m + 1, i, min((lim - b[i]) / 2. / a[i], (double)c[i]));
                      for (int i = 1; i <= n; i++)
                          for (int j = 1; j <= m; j++)
                              if (con[i][j]) addEdge(i, n + j, 1e18);
                      for (int i = 1; i <= m; i++) addEdge(n + i, n + m + 2, d[i]);
                      while (bfs()) dfs(n + m + 1, 1e18);
                      Frac K, B;
                      for (int i = 1; i <= n; i++)
                          if (dist[i] == -1) {
                              if (a[i] == 0) {
                                  if (b[i] < lim) B += Frac(c[i]);
                              } else if (lim > 2 * a[i] * c[i] + b[i])
                                  B += Frac(c[i]);
                              else if (lim > b[i])
                                  K += Frac(1, 2 * a[i]), B -= Frac(b[i], a[i] * 2);
                          }
                      for (int i = 1; i <= m; i++)
                          if (~dist[n + i]) B += Frac(d[i]);
                      return {K, B};
                  }
              } net;
              
              vector<pff> nodes;
              
              void solve(pff l, pff r) {
                  if (l == r) return;
                  Frac mid = (l.second - r.second) / (r.first - l.first);
                  pff fml = net.dinic((double)mid - eps), fmr = net.dinic((double)mid + eps);
                  if (l == fml) return nodes.emplace_back(mid, fml.first * mid + fml.second), void();
                  return solve(l, fml), solve(fmr, r);
              }
              
              void solve(void) {
                  cin >> n >> m;
                  for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
                  for (int i = 1; i <= m; i++) cin >> d[i];
                  for (int i = 1; i <= n; i++)
                      for (int j = 1; j <= m; j++) cin >> con[i][j];
                  cout << int64_t(net.dinic(1e18).second) << endl;
                  nodes.emplace_back(Frac(), Frac());
                  for (int i = 1; i <= 3; i++) {
                      auto l = net.dinic(i - 1 + eps), r = net.dinic(i - eps);
                      solve(l, r);
                      nodes.emplace_back(Frac(i), Frac(i) * r.first + r.second);
                  }
                  solve(net.dinic(3 + eps), net.dinic(1e18));
                  Frac ans;
                  for (int i = 1; i < (int)nodes.size(); i++) {
                      pff f1 = net.dinic((double)nodes[i - 1].first + eps), f2 = net.dinic((double)nodes[i].first - eps),
                          f3 = net.dinic((double)nodes[i].first + eps);
                      ans += Frac(1, 2) * (nodes[i].second - f1.first * nodes[i - 1].first - f1.second) *
                                 (nodes[i - 1].first + nodes[i].first) +
                             nodes[i].first * (f3.first * nodes[i].first + f3.second - f2.first * nodes[i].first - f2.second);
                  }
                  ans.print(), cout << endl;
                  return;
              }
              
              bool mem2;
              
              int main() {
                  ios::sync_with_stdio(false), cin.tie(nullptr);
              #ifdef LOCAL
                  cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
              #endif
              
                  int _ = 1;
                  while (_--) solve();
              
              #ifdef LOCAL
                  cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
              #endif
                  return 0;
              }
              
              
              ❤️ 6
              👍 6
            • @ 2022-6-30 7:29:45

              #033 2022.6.30

              codeforcesP1667F Yin Yang

              标签:构造,*3500

              给定一个 4n×4m4n\times 4m 的方格图,每个格子都是黑色或白色。有些格子已经被涂色了,你要给剩下的格子涂色,使得黑色格子和白色格子分别组成连通块。构造一种方案或判断无解。

              保证已经被涂色的格子没有公共点或公共边。

              44n,4m5004\leq 4n,4m\leq 500,多组数据,数据组数 4000\leq4000,保证 nm250000\sum nm \leq 250000

              题解

              如果四个边界上没有格子被染色,是一个经典套路,考虑构造“梳子”状的图案,如图 1:

              图 1

              因为任意两个限制颜色的格子不八联通,这种方案一定是可行的。

              然后考虑如果边界上有限制颜色的格子。若边界上存在形如 BWBW 的序列,是一定无解的,如图 2(格子上有“限制”二字表示这个格子颜色固定):

              图 2

              对于不存在形如 BWBW 序列的情况,不难发现,我们一定可以找到完整的一个边界(上/下/左/右),这条边上可以全部赋成同一个颜色,而且它对面那条边界上至少有一个点是不同的颜色。不妨把这个完整的边界上的颜色当成蓝色,参考图 1 “梳子”型构造的蓝色部分,给它安排好。以保证蓝色的格子相互之间可以连通了。现在处理红色格子,可以列举出如下三个不合法的情况,我们一一解决:

              1. 边框被蓝色包围了,部分边框上的红色与梳子的条纹不联通。
              2. 接近边框位置(第 22 和第 n1n-1 行)的格子不联通。
              3. 红色梳子条纹不联通。

              图 3 的三个例子分别对应了上面的三种不合法情况:

              图 3

              实际上这三种情况都可以通过简单的调整实现:

              1. 把下面也变成蓝色。(显然)
              2. 直接把道路打通就可以了,因为旁边的蓝色一定是连通的(考虑 BWBW 情况已经没有了,如果不联通就扩充直到顶到一个限制红色的格子门口)。
              3. 打穿一个蓝色条纹即可,这一步在实现情况二之后进行,就无需考虑被打穿的蓝色条纹左右不联通了(两边的条纹会沿着一条边界连起来)。

              此外还有很多零零散散的细节,例如解决这三种情况的顺序,等等。

              代码(长代码注意)
              #include<bits/stdc++.h>
              #define int long long
              using namespace std;
              bool Begin;
              const int max_n=502;
              inline int read(){
                  int x=0;bool w=0;char c=getchar();
                  while(c<'0' || c>'9') w|=c=='-',c=getchar();
                  while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
                  return w?-x:x;
              }
              inline void write(int x){
                  putchar(x==2?'B':'W');
              }
              inline int reads(){
                  char c=getchar();
                  while(c!='B' && c!='W' && c!='.') c=getchar();
                  if(c=='B') return 2;
                  if(c=='W') return 3;
                  return 0;
              }
              
              int n,m,cntr;
              int a[max_n][max_n],ans[max_n][max_n];
              
              int Tmp[max_n][max_n];
              inline void rotate(){
                  for(register int i=1;i<=n;++i)
                      for(register int j=1;j<=m;++j)
                          Tmp[i][j]=a[i][j];
                  for(register int i=1;i<=n;++i)
                      for(register int j=1;j<=m;++j)
                          a[j][n-i+1]=Tmp[i][j];
                  for(register int i=1;i<=n;++i)
                      for(register int j=1;j<=m;++j)
                          Tmp[i][j]=ans[i][j];
                  for(register int i=1;i<=n;++i)
                      for(register int j=1;j<=m;++j)
                          ans[j][n-i+1]=Tmp[i][j];
                  swap(n,m),++cntr;
              }
              inline void clear(){
                  cntr=0;
                  for(register int i=0;i<=n;++i)
                      for(register int j=0;j<=m;++j)
                          a[i][j]=ans[i][j]=a[j][i]=ans[j][i]=0;
              }
              
              inline int calc(){
                  int res=0;
                  for(register int p=1;p<=2;++p){
                      for(register int i=2;i<=m;++i)
                          if(!ans[1][i])
                              ans[1][i]=ans[1][i-1];
                      for(register int i=2;i<=n;++i)
                          if(!ans[i][m])
                              ans[i][m]=ans[i-1][m];
                      for(register int i=m-1;i;--i)
                          if(!ans[n][i])
                              ans[n][i]=ans[n][i+1];
                      for(register int i=n-1;i;--i)
                          if(!ans[i][1])
                              ans[i][1]=ans[i+1][1];
                      if(!ans[1][1])
                          ans[1][1]=2;
                  }
                  for(register int i=2;i<=m;++i)
                      if(ans[1][i]!=ans[1][i-1])
                          ++res;
                  for(register int i=2;i<=n;++i)
                      if(ans[i][m]!=ans[i-1][m])
                          ++res;
                  for(register int i=m-1;i;--i)
                      if(ans[n][i]!=ans[n][i+1])
                          ++res;
                  for(register int i=n-1;i;--i)
                      if(ans[i][1]!=ans[i+1][1])
                          ++res;
                  return res;
              }
              
              inline bool Nice(){
                  bool ok=0;
                  for(register int i=1;i<=n;++i){
                      if(ans[i][1]!=ans[1][1])
                          return 0;
                      if(i>1 && i<n && ans[i][m]!=ans[1][1])
                          ok=1;
                  }
                  return ok;
              }
              
              int Red,Blue;
              
              inline void findroad(int x,int y){
                  if(ans[x-1][y]==Red || ans[x+1][y]==Red || ans[x][y+1]==Red) return;
                  int X1=(x==2?1:n);
                  if(y<=m-2 && ans[X1][y+2]==Red){
                      ans[X1][y]=ans[X1][y+1]=Red;
                      return;
                  }
                  int X2=(x==2?2:n-1);
                  if(y<=m-2 && ans[X2][y+2]==Red){
                      ans[X2][y+1]=Red;
                      return;
                  }
                  int X3=(x==2?3:n-2),X4=(x==2?4:n-3);
                  if(a[X4][y]!=Blue){
                      ans[X3][y]=Red;
                      return;
                  }
                  int Y=(y<=m-2?y+1:y-1);
                  ans[X2][Y]=ans[X3][Y]=Red;
              }
              
              inline void bigroad(int x){
                  for(register int j=2;j<=4;++j){
                      bool ok=1;
                      for(register int i=x-1;i<=x+2;++i)
                          if(a[i][j]==Blue){
                              ok=0;
                              break;
                          }
                      if(ok){
                          ans[x][j]=ans[x+1][j]=Red;
                          return;
                      }
                  }
                  for(register int i=x-1;i<=x+2;++i)
                      if(!a[i][3])
                          ans[i][3]=Red;
                  if(a[x-1][3]){
                      ans[x-1][2]=Blue,
                      ans[x][4]=Red;
                  }
                  if(a[x+2][3]){
                      ans[x+2][2]=Blue,
                      ans[x+1][4]=Red;
                  }
                  if(a[x][3] || a[x+1][3]){
                      ans[x][2]=ans[x+1][2]=Red;
                  }
              }
              
              inline void buildroad(){
                  int fr=0,ls=0;
                  for(register int i=1;i<=n;++i)
                      if(ans[i][m]==Red){
                          if(!fr) fr=i;
                          ls=i;
                      }
                  if(!fr || (ls>3 && fr<n-2)) return;
                  if(ls<=3 && a[4][m-1]==Blue){
                      ans[3][m]=ans[4][m]=ans[5][m]=Red;
                      return;
                  }
                  if(fr>=n-2 && a[n-3][m-1]==Blue){
                      ans[n-4][m]=ans[n-3][m]=ans[n-2][m]=Red;
                      return;
                  }
                  int x=(ls<=3?2:n-2);
                  for(register int i=x;i<=x+1;++i)
                      for(register int j=m-1;j<=m;++j)
                          if(!a[i][j])
                              ans[i][j]=Red;
              }
              
              bool End;
              #define File ""
              signed main(){
                  // #ifndef ONLINE_JUDGE
                  // freopen(File ".in","r",stdin);
                  // freopen(File ".out","w",stdout);
                  // #endif
                  for(register int T=read();T;--T,clear()){
                      n=read(),m=read();
                      for(register int i=1;i<=n;++i)
                          for(register int j=1;j<=m;++j)
                              a[i][j]=ans[i][j]=reads();
                      int tmp=calc();
                      if(tmp>=4){
                          puts("NO");
                          continue;
                      }
                      if(tmp>0) while(!Nice()) rotate();
                      Blue=ans[1][1],Red=Blue^1;
                      for(register int i=2;i<n;++i)
                          for(register int j=2;j<m;++j)
                              if(!a[i][j])
                                  ans[i][j]=(i%4>1?Blue:Red);
                      for(register int i=1;i<n;++i)
                          if(ans[i][m-1]==ans[i+1][m] && ans[i+1][m-1]==ans[i][m] && ans[i][m]!=ans[i+1][m]){
                              if(!a[i][m]) ans[i][m]^=1;
                              else ans[i+1][m]^=1;
                          }
                      buildroad();
                      for(register int i=2;i<m;++i){
                          if(a[2][i]==Red) findroad(2,i);
                          if(a[n-1][i]==Red) findroad(n-1,i);
                      }
                      for(register int i=6;i<=n-6;i+=4)
                          if(ans[i][m]==Blue || ans[i+1][m]==Blue)
                              bigroad(i);
                      while(cntr%4!=0) rotate();
                      puts("YES");
                      for(register int i=1;i<=n;++i){
                          for(register int j=1;j<=m;++j)
                              write(ans[i][j]);
                          putchar('\n');
                      }
                  }
                  return 0;
              }
              
              👍 7
              ❤️ 3
              • @ 2022-6-29 8:58:29

                #032 2022.6.29

                [JSOI2019]节日庆典

                标签:字符串,lyndon 分解,exkmp。

                Statement

                给定一个串 SS,求每个前缀的最小表示法。

                Data Range:1n3×106\textbf{Data Range:}1\leq n \leq 3 \times10^6

                Solution

                Solution

                考虑 lyndon 分解,如果我们对每个前缀都跑一遍 lyndon 分解的话,答案应该是最后一个开头 i\leq i 的 lyndon 串。

                这样不优秀啊,但是我们仍然考虑 lyndon 分解。

                假设我们现在维护的是 putvpu^tv,仍然维护指针 i,j,ki,j,k

                我们其实当前位置要加入的一个字符 kk 的最小表示法的开头只会有两种情况,一种是在我的当前开始的位置 ii,一种是在我加入的这个 vv 里面的。

                vv 里面的话,你考虑他最终的表示法会是什么样子,比如 putvpu^tv,那么最终他会是 vputvpu^t

                你仔细发现,反正我没发现,然后你发现如果你去掉最后的 u|u| 个字符,他就会变成 vput1vpu^{t-1},然后这就是一个已经求解过的答案了,他是 put1vpu^{t-1}v 的最小表示法。

                现在我们需要根据 SjS_jSkS_k 的大小进行分类。

                如果 Sj<SkS_j < S_k,那么根据 lyndon 串的性质,那么 utv+Sku^tv+S_k 仍然是一个 lyndon 串,那么此时的 ii 就是我们的 anskans_k

                如果 Sj>SkS_j > S_k,那么之前的 lyndon 串被划分了出来,但是当前位置仍然不知道,于是我们将其放到后面进行求解。

                如果 Sj=SkS_j = S_k,那么可以选择两种位置,首先就是当前的 ii 可以作为 anskans_k,另一种是,先前循环节中 kk 的对应位置 jj 的答案向后移一个循环节的对应位置 ansj+kjans_j + k - j

                那么需要比较的为 S[ik]+S[1(i1)]S[i\dots k] + S[1 \dots (i - 1)]S[(ansj+kj)k]+S[1ansj+kj1]S[(ans_j + k - j) \dots k] + S[1\dots ans_{j} + k - j - 1] 的字典序大小。

                首先我们只会在 Sj=SkS_j = S_k 的时候遇到这种情况,那么 S[i(i+k(ansj+kj))]S[i \dots (i + k - (ans_j + k - j))]S[(ansj+kj)k]S[(ans_j + k - j) \dots k] 肯定都是相同的。

                如下图:

                也就是说上面的 S2S_2S4S_4 一定是相同的。

                然后你分着来比较,先比较 S3+S4S_3 + S_4 和与他对应长度的那一部分。

                也就是图中画着绿线的那一部分,然后再比较后面的剩下部分就好了。

                这样你发现,每次都是将一个子串 S[ab]S[a \dots b] 与原串的一个前缀 S[1ba+1]S[1 \dots b - a + 1] 进行比较。

                那么我们可以使用 zz 函数,判断后缀 aa 与原串的一个 lcp 长度判断是否再比较范围内,并找到这个不同即可。

                使用 exkmp\text{exkmp} 可以求解。

                于是直接跑 Duval 算法就好了,复杂度 O(n)O(n),真神仙。

                // 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱
                // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱!
                // 没有力量的理想是戏言,没有理想的力量是空虚
                // Problem: P5334 [JSOI2019]节日庆典
                // Contest: Luogu
                // Memory Limit: 500 MB
                // Time Limit: 1000 ms
                // The Author : Pt
                #include <bits/stdc++.h>
                using namespace std;
                namespace io {
                  const int SIZE = (1 << 21) + 1; char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
                  #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
                  inline void flush () {  fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
                  inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
                  template <class I> inline void gi (I &x) { for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f; }
                  string getstr(void) { string s = ""; char c = gc(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = gc(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF))s.push_back(c), c = gc(); return s;}
                  template <class I> inline void print (I x) { if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) putc (qu[qr --]); }
                  struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
                }
                using io :: gi;  using io :: putc;  using io :: print;
                #define V inline void
                #define I inline int
                template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
                template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
                #define rep(i, l, r) for (int i = (l); i <= (r); i++)
                #define repd(i, l, r) for (int i = (l); i >= (r); i--)
                const int N = 3e6 + 5;
                char S[N];
                int z[N], n, ans[N];
                void exkmp() {
                  z[1] = n;
                  for (int i = 2, l = 0, r = 0; i <= n; i++) {
                    if (i <= r)  z[i] = min(z[i - l + 1], r - i + 1);
                    while (i + z[i] <= n && S[i + z[i]] == S[1 + z[i]]) ++ z[i];
                    if (i + z[i] - 1 > r)  r = i + z[l = i] - 1;
                  }
                }
                int compare(int x,int y,int r) {
                  if (x == y)  return x;
                  int zz = z[x + r - y + 1];
                  if (zz < y - x)  return S[x + r - y + 1 + zz] < S[1 + zz] ? x : y;
                  zz = z[y - x + 1];
                  if (zz < x - 1)  return S[1 + zz] < S[y - x + 1 + zz] ? x : y;
                  return x;
                }
                void solve() {
                  int i = 1;
                  while (i <= n) {
                    int j = i, k = i + 1;
                    if (!ans[i])  ans[i] = i;
                    while (k <= n && S[j] <= S[k]) {
                      if (S[j] < S[k]) {
                        if (!ans[k])  ans[k] = i;  j = i;  ++k;
                      }  else {
                        if (!ans[k]) {
                          if (ans[j] < i)  ans[k] = i;
                          else  ans[k] = compare(i, ans[j] + k - j, k);
                        }
                        ++k;  ++j;
                      }
                    }
                    int len = k - j;
                    while (i <= j)  i += len;
                  }
                }
                signed main () {
                #ifdef LOCAL_DEFINE
                  freopen("input.txt", "r", stdin);
                #endif
                  cin >> (S + 1);  n = strlen(S + 1);
                  exkmp();  solve();
                  rep (i, 1, n)  cout << ans[i] << " ";
                #ifdef LOCAL_DEFINE
                  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
                #endif
                  return 0;
                }
                
                👍 8
                ❤️ 5
              • @ 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;
                }
                
                👍 10
                👀 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;
                }
                
                👍 10
                ❤️ 6
                • @ 2022-4-15 22:18:26

                  弱弱地问一下,后面的标签是如何打出来的啊?

                • @ 2022-5-3 9:13:15

                  Hydro 每月一题(逃

                • @ 2022-5-29 17:26:44

                  @ html

              • @ 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)

                👍 9
                ❤️ 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;
                      }
                      
                      ❤️ 1
                      • @ 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;
                          }
                          
                          ❤️ 1
                          • @ 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 次,因此全局总共花在暴力递归上的复杂度为