## 【日常小测】异或与区间加

### Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
using namespace std;

const int N = 150009;
const int MOD = 1073741824;
const int blk_sz = 800;

int n, m, k, a[N];
UI a1[N], ans[N], blk_tag[N], tag[N];
vector<int> num, pos_list[N];
vector<pair<int, int> > left_list[N], right_list[N];
struct Query{
int l, r, w;
inline bool operator < (const Query &QQQ) const {
return r > QQQ.r;
}
}q[N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline int find(int x) {
int l = 0, r = num.size() - 1, mid;
while (l <= r) {
mid = l + r >> 1;
if (num[mid] == x) {
return mid;
} else if (num[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}

inline void solve(int A, int B) {
static UI a2[N], cur;
memset(a2, 0, sizeof(a2));
for (int i = 1; i <= n; i++) {
a2[i] = a2[i - 1] + (a[i] == num[B]);
}
cur = 0;
for (int i = n; i; i--) {
if (a[i] == num[B]) {
cur += a1[i];
}
if (a[i - 1] == num[A]) {
ans[i] += cur;
}
for (int j = 0; j < (int)left_list[i].size(); ++j) {
cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]);
}
}
memset(a2, 0, sizeof(a2));
for (int i = 1; i <= n; ++i) {
a2[i] = a2[i - 1] + (a[i - 1] == num[A]);
}
cur = 0;
for (int i = 1; i <= n; i++) {
if (a[i - 1] == num[A]) {
cur -= a1[i];
}
if (a[i] == num[B]) {
ans[i + 1] += cur;
}
for (int j = 0; j < (int)right_list[i].size(); ++j) {
cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]);
}
}
}

int main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
num.push_back(0);
for (int i = 1; i <= n; ++i) {
a[i] = a[i - 1] ^ read();
num.push_back(a[i]);
}
sort(num.begin(), num.end());
num.resize(unique(num.begin(), num.end()) - num.begin());
for (int i = 0; i <= n; i++) {
int pp = find(a[i]);
pos_list[pp].push_back(i);
}
for (int i = 1, l, r, w; i <= m; ++i) {
left_list[l].push_back(make_pair(r, w));
right_list[r].push_back(make_pair(l, w));
a1[l] += w;
a1[r + 1] -= w;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= n; ++i) {
a1[i] += a1[i - 1];
}
for (int i = 0; i < (int)num.size(); i++) {
int r = i, l = find(num[i] ^ k);
if (l != -1 && (int)pos_list[l].size() > blk_sz) {
solve(l, r);
}
}
for (int r = n, cur = 0; r; r--) {
while (cur < m && q[cur + 1].r >= r) {
++cur;
for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) {
tag[i] += q[cur].w;
}
for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) {
blk_tag[i] += q[cur].w;
}
for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) {
tag[i] += q[cur].w;
}
}
int t = find(a[r] ^ k);
if (t != -1 && (int)pos_list[t].size() <= blk_sz) {
for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) {
int l = pos_list[t][tt] + 1;
if (l <= r) {
ans[l] += tag[l] + blk_tag[l / blk_sz];
ans[r + 1] -= tag[l] + blk_tag[l / blk_sz];
} else {
break;
}
}
}
}
for (int i = 1; i <= n; i++) {
ans[i] += ans[i - 1];
printf("%d ", ans[i] % MOD);
}
return 0;
}


## 【UOJ 246】[UER #7] 套路

### 解题报告

1. 考虑 $len<S$ 的情况
我们枚举右端点，暴力向左扫 $S$ 个就可以了

2. 考虑 $len \ge S$ 的情况
我们发现相似度不会超过 $\frac{m}{{len – 1}}$
于是考虑在权值上暴力向两边扫 $S$ 个

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
K = read(); S = sqrt(m) + 1;
for (int i=1;i<=n;i++) a[i] = read();

memset(gap,60,sizeof(gap));
for (int i=1;i<=n;i++) {
for (int j=i-1;j>=i-S&&j;--j) {
gap[j] = min(gap[j], gap[j+1]);
gap[j] = min(gap[j], abs(a[i] - a[j]));
if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
}
}
memset(gap,0,sizeof(gap));
for (int i=1;i<=n;i++) {
for (int j=0;j<=S;j++) {
if (j) gap[j] = max(gap[j], gap[j-1]);
if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1));
}
lst[a[i]] = i;
}
printf("%lld\n",vout);
return 0;
}