【YBT2023寒假Day4 C】櫻桃莓莓（互動）（四毛子分塊）（線段樹）

櫻桃莓莓

題目連結：YBT2023寒假Day4 C

題目大意

有一個黑盒操作滿足交換律和結合律，有 n 個數，q 次詢問，每次選 m 個下标，你要計算所有不包含那 m 個下标的數進行黑盒操作之後的結果。

預處理不超過 4n 次，每次詢問不超過 4(m+1) 次。（這裡的一次是指使用一次黑盒操作）

思路

第一步想到的應該是字首字尾，但是中間的要怎麼辦呢。

考慮分塊（有點四毛子的感覺），求出每一塊的字首字尾。

但是發現怎麼都還是會超 4 n 4n 4n，那這個時候考慮不要了整個的字首字尾，思考超 4 n 4n 4n 的原因。

就是一個塊 [ x , y ] [x,y] [x,y] 内如果 [ x + 1 , y − 1 ] [x+1,y-1] [x+1,y−1] 問這個就寄了。

（塊長小的話要拼的也太多了）

那考慮每個塊中間你在弄一個點，從這個點往前和往後在處理一遍。

（那現在是 3 n 3n 3n）

先看看夠不夠，發現當 B = 8 B=8 B=8 的時候，如果小塊的詢問沒有跨越中間的部分，那它長度至多是 4 4 4，我們就可以暴力一個一個點并起來查詢。

那小塊就可以了，接着搞大塊，考慮怎麼辦。

試着能不能用線段樹的結構，會發現好像如果要這樣的話，你合并的時候時間又超了。

考慮分攤一下，分攤到預處理那裡，于是考慮線段樹每個位置你都處理一個字首字尾。

然後到詢問第一次裂成兩半的時候，你就可以直接分别用那兩半的字尾和字首直接拼出來。

于是數一數行不行。

如果整個詢問是小塊，至多是 4 4 4 可以。

如果詢問分成兩個小塊和大段，每個小塊由于分出來的一定是字首或者字尾，大段我們用線段樹的的方法至多 2 2 2 次，也是 4 4 4。

然後看初始化，前面的是 3 n 3n 3n，考慮給線段樹那個部分是多少。

注意線段樹是把段分線段樹的，是以總的是 2 n / 8 log ⁡ n / 8 2n/8\log n/8 2n/8logn/8，會發現超了。

不過其實這個 2 2 2 可以去掉，因為一個線段樹上的點要麼是隻用字首，要麼是隻用字尾（根據它下标的奇偶， 1 1 1 就不會有）

是以就是 n / 8 log ⁡ n / 8 n/8\log n/8 n/8logn/8，大概是 1901 1901 1901 左右當 n = 2000 n=2000 n=2000，就 < n <n <n，是以是可以的。

代碼

#include <algorithm>
#include <vector>
#include <cstdio>
#include <set>
#include "blackbox.h"
#define ull unsigned long long

using namespace std;

const int N = 10000;
int n, m, B = 8, blo[N], bl[N], br[N];
ull pre[N], suf[N], Mid[N], b[N];

struct XD_tree {
	ull f[N][N];
	
	void build(int now, int l, int r) {
	    if (now != 1) {
	        if (now & 1) {
	            f[now][l] = pre[br[l]];
	            for (int j = l + 1; j <= r; j++) f[now][j] = magic(f[now][j - 1], pre[br[j]]);
	        } else {
	            f[now][r] = pre[br[r]];
	            for (int j = r - 1; j >= l; j--) f[now][j] = magic(f[now][j + 1], pre[br[j]]);
	        }
	    }
	    if (l == r) return;
	    int mid = (l + r) >> 1;
	    build(now << 1, l, mid);
	    build(now << 1 | 1, mid + 1, r);
	}
	
	ull query(int now, int l, int r, int L, int R) {
	    if (L <= l && r <= R) {
	        if (now & 1) return f[now][r];
	        	else return f[now][l];
	    }
	    int mid = (l + r) >> 1;
	    if (L <= mid && mid < R) return magic(f[now << 1][L], f[now << 1 | 1][R]);
	    if (L <= mid) return query(now << 1, l, mid, L, R);
	    if (mid < R) return query(now << 1 | 1, mid + 1, r, L, R);
	}
}T;

void init(vector <ull> a, int M) {
    n = a.size(); m = M;
    for (int i = 1; i <= n; i++) b[i] = a[i - 1], blo[i] = (i - 1) / B + 1;
    for (int i = 1; i <= blo[n]; i++) {
    	bl[i] = (i - 1) * B + 1; br[i] = min(n, i * B); int l = bl[i], r = br[i];
        pre[l] = b[l]; for (int j = l + 1; j <= r; j++) pre[j] = magic(pre[j - 1], b[j]);
        suf[r] = b[r]; for (int j = r - 1; j >= l; j--) suf[j] = magic(suf[j + 1], b[j]);
        int mid = min(n, l + 3);
        Mid[mid] = b[mid]; for (int j = mid - 1; j >= l; j--) Mid[j] = magic(Mid[j + 1], b[j]);
        if (mid != r) {
            Mid[mid + 1] = b[mid + 1]; for (int j = mid + 2; j <= r; j++) Mid[j] = magic(Mid[j - 1], b[j]);
        }
    }
	T.build(1, 1, blo[n]);
}

ull slove(int l, int r) {
    if (blo[l] == blo[r]) {
        int mid = blo[l] + 3;
        if (r - l + 1 > 4) return magic(Mid[l], Mid[r]);
        ull re = b[l];
        for (int i = l + 1; i <= r; i++) re = magic(re, b[i]);
        return re;
    }
    ull re = magic(suf[l], pre[r]);
    if (blo[l] != blo[r] - 1) re = magic(re, T.query(1, 1, blo[n], blo[l] + 1, blo[r] - 1));
    return re;
}

ull query(vector <int> u) {
    sort(u.begin(), u.end());
    ull ans = 0;
    int las = 0, nof = 0;
    for (int i = 0; i < m; i++) {
        int l = las + 1, r = u[i];
        if (l <= r) {
            if (!nof) nof = 1, ans = slove(l, r);
            	else ans = magic(ans, slove(l, r));
        }
        las = u[i] + 1;
    }
    if (las != n) {
        if (!nof) ans = slove(las + 1, n);
        	else ans = magic(ans, slove(las + 1, n));
    }
    return ans;
}