Description：

有一个数列 $a$ ，有一个运算 $magic(x,y)$ ，保证满足交换律和结合律，每次删去黑盒中的 $m$ 个元素，并求剩下的元素作 $magic$ 运算后的值。

$n\leqslant 2000, 2^m\leqslant n, 0\leqslant a_i<2^{64}$

交互题，要求预处理的 $magic$ 次数不超过 $4n$ ，单次询问 $magic$ 次数不超过 $4(m+1)$ 。

Solution：

直接线段树肯定是不行的，有一个神奇的做法叫做 $Method\ of\ Four\ Russians$ ，也就是说在预处理的时候每 $8$ 个分一段，每一段内预处理前后缀和，消耗 $2n$ 个询问，然后对于所有整块的，用一棵线段树维护，在线段树的每一层预处理前后缀和，消耗 $(n/8)\log (n/8)\leqslant 2n$ 个询问，类似于分治，如果只在左半边就只进入左半边，否则进入右半边，这样在线段树上查询一次只消耗 $1$ 个询问，查询时除去删掉的 $m$ 个元素，还有 $m+1$ 段，对着 $m+1$ 段分别求答案，最后合并，合并消耗 $m+1$ 个询问，也就是说我们最后单次询问均摊下来不能超过 $3$ 个询问，如果两个端点分别在不同的块中，那么消耗恰好三个询问（左边零散的和中间大块的合并，中间大块的的在线段树上计算，最后和右边的合并），如果在一个块中那么如果是前后缀直接回答，否则就暴力扫，但是这样一次最多消耗 $5$ 个询问，但实际上如果有一边顶到块的边界了，他边界的另一边那个块就没有另一边零散的部分了，可以画个图理解，因此均摊下来询问数还是不超过 $3$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#include"blackbox.h"

typedef unsigned long long ull;

#define MAXN 2070

int nn;

ull s[MAXN];

ull ss[15][MAXN];

ull sum1[MAXN],sum2[MAXN];

ull sum[MAXN];

int belong[MAXN],L[MAXN],R[MAXN];

int blo,tot;

#define mid ((l + r) >> 1)

map<pair<ull,ull>,ull> mem;

inline ull mymagic(ull a,ull b)

{

	if(a > b)swap(a,b);

	if(mem.find(make_pair(a,b)) != mem.end())return mem[make_pair(a,b)];

	return mem[make_pair(a,b)] = magic(a,b);

}

void build(int d,int l,int r)

{

	if(l == r)return;

	build(d + 1,l,mid);

	build(d + 1,mid + 1,r);

	ss[d][mid] = sum[mid];

	for(int i = mid - 1;i >= l;--i)ss[d][i] = mymagic(sum[i],ss[d][i + 1]);

	ss[d][mid + 1] = sum[mid + 1];

	for(int i = mid + 2;i <= r;++i)ss[d][i] = mymagic(sum[i],ss[d][i - 1]);

	return;

}

void init(vector<ull> a,int m)

{

	nn = a.size();

	for(int i = 1;i <= nn;++i)s[i] = a[i - 1];

	blo = 8;

	for(int i = 1;i <= nn;++i)

	{

		belong[i] = (i - 1) / blo + 1;

		if(L[belong[i]] == 0)L[belong[i]] = i;

		R[belong[i]] = i;

	}

	tot = belong[nn];

	for(int i = 1;i <= tot;++i)

	{

		sum1[L[i]] = s[L[i]];

		for(int j = L[i] + 1;j <= R[i];++j)sum1[j] = mymagic(sum1[j - 1],s[j]);

		sum2[R[i]] = s[R[i]];

		for(int j = R[i] - 1;j > L[i];--j)sum2[j] = mymagic(sum2[j + 1],s[j]);

		sum2[L[i]] = sum[i] = sum1[R[i]];

	}

	build(1,1,tot);

	return;

}

ull query(int d,int L,int R,int l,int r)

{

	if(l == r)return sum[l];

	if(R <= mid)return query(d + 1,L,R,l,mid);

	if(L > mid)return query(d + 1,L,R,mid + 1,r);

	return mymagic(ss[d][L],ss[d][R]);

}

ull calc(int l,int r)

{

	if(belong[l] == belong[r])

	{

		ull res = s[l];

		for(int i = l + 1;i <= r;++i)res = mymagic(res,s[i]);

		return res;

	}

	int lef = belong[l],rig = belong[r];

	ull res;

	bool first = true;

	if(l != L[lef])

	{

		++lef;

		if(first)res = sum2[l],first = false;

		else res = mymagic(res,sum2[l]);

	}

	if(r != R[rig])

	{

		--rig;

		if(first)res = sum1[r],first = false;

		else res = mymagic(res,sum1[r]);

	}

	if(lef <= rig)

	{

		if(first)res = query(1,lef,rig,1,tot);

		else res = mymagic(res,query(1,lef,rig,1,tot));

	}

	return res;

}

ull query(vector<int> u)

{

	u.push_back(nn);

	sort(u.begin(),u.end());

	ull ans = 0;

	int last = 1;

	bool first = true;

	for(int x = 0; x < u.size(); ++x)

	{

		++u[x];

		if(u[x] > last)

		{

			ull res = calc(last,u[x] - 1);

			if(first)ans = res,first = false;

			else ans = mymagic(ans,res);

		}

		last = u[x] + 1;

	}

	return ans;

}