由于题目名称非常简洁，并且没有任何新意，所以……
T1 Apj
考虑如何判断一个区间是否合法，首先找到区间内所有奇数的位置，显然这些位置需要通过 \(2\) 操作变为 \(0\) ，因此一个比较显然的条件是这些位置的个数必须为偶数，考虑将区间变为 \(0\) 的过程，简单模拟不难发现相邻两个奇数位置两两匹配所构成的方案最优，因为同时消去两个奇数位置至少会使两个位置之间的区间减 \(2\) ，而相邻位置匹配不存在重叠区间。因此我们需要保证相邻奇数位置区间 \(\min\ge 2\) （严谨来讲是第一个位置和第二个位置之间的区间，第三个位置和第四个位置之间的区间……以此类推，这样的区间 \(\min\ge 2\) ）
简化一下判断条件，一个区间合法当且仅当这段区间被 \(0\) 分割成的每个子区间的区间和为偶数，一个比较显然的想法是离线后做扫描线，维护区间历史版本和即可。
此时产生一个邪恶的想法：强制在线！（其实就是我在考场上脑瘫了）
于是抛弃扫描线做法，我们直接维护一个线段树，考虑两个区间的合并。
只需要考虑简单的几种情况即可。
发现跨过分治中心的合法区间只存在两种情况：左右同时存在偶数个权值为奇数的位置和左右同时存在奇数个权值为奇数的位置。
因此在每个区间 \([L,R]\) 维护存在多少个位置 \(i\) ，满足 \([i,R]\) 区间是一个合法的区间，但由于区间合并时需要考虑存在奇数个权值为奇数的情况，实际上需要维护是否省略最左边权值为奇数的位置，是否省略最右边权值为奇数的位置，满足 \([i,R]\) 是一个合法区间的 \(i\) 的个数。
同理维护合法的 \([L,i]\) 的个数即可。
然后你得到了一个长达 \(100\) 行的 Push_Up……
但没关系，总复杂度仍然是 \(O(n\log n)\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 5e5;
const int inf = 0x3f3f3f3f;
int n, q, a[max1 + 5], minval[max1 + 5];
struct Data
{
long long sum;
int countL[2][2], countR[2][2], posL, posR, count;
bool legalL[2], legalR[2];
Data operator + ( const Data &A ) const
{
Data res;
res.sum = sum + A.sum;
res.sum += 1LL * countL[0][0] * A.countR[0][0];
if ( posR != -1 && A.posL != -1 && minval[posR] )
res.sum += 1LL * countL[0][1] * A.countR[1][0];
res.countL[0][0] = A.countL[0][0];
res.countL[0][1] = A.countL[0][1];
res.countL[1][0] = A.countL[1][0];
res.countL[1][1] = A.countL[1][1];
if ( A.count & 1 )
{
if ( A.legalR[0] )
{
if ( posR != -1 && A.posL != -1 && minval[posR] )
{
res.countL[0][0] += countL[0][1];
res.countL[1][0] += countL[1][1];
}
}
if ( A.legalR[1] )
{
res.countL[0][1] += countL[0][0];
res.countL[1][1] += countL[1][0];
}
}
else
{
if ( A.legalR[0] )
{
res.countL[0][0] += countL[0][0];
res.countL[1][0] += countL[1][0];
}
if ( A.legalR[1] )
{
if ( posR != -1 && A.posL != -1 && minval[posR] )
{
res.countL[0][1] += countL[0][1];
res.countL[1][1] += countL[1][1];
}
}
else
{
if ( A.posL == -1 )
{
res.countL[0][1] += countL[0][1];
res.countL[1][1] += countL[1][1];
}
}
}
res.countR[0][0] = countR[0][0];
res.countR[0][1] = countR[0][1];
res.countR[1][0] = countR[1][0];
res.countR[1][1] = countR[1][1];
if ( count & 1 )
{
if ( legalL[0] )
{
if ( posR != -1 && A.posL != -1 && minval[posR] )
{
res.countR[0][0] += A.countR[1][0];
res.countR[0][1] += A.countR[1][1];
}
}
if ( legalL[1] )
{
res.countR[1][0] += A.countR[0][0];
res.countR[1][1] += A.countR[0][1];
}
}
else
{
if ( legalL[0] )
{
res.countR[0][0] += A.countR[0][0];
res.countR[0][1] += A.countR[0][1];
}
if ( legalL[1] )
{
if ( posR != -1 && A.posL != -1 && minval[posR] )
{
res.countR[1][0] += A.countR[1][0];
res.countR[1][1] += A.countR[1][1];
}
}
else
{
if ( posR == -1 )
{
res.countR[1][0] += A.countR[1][0];
res.countR[1][1] += A.countR[1][1];
}
}
}
if ( posL == -1 )
res.posL = A.posL;
else
res.posL = posL;
if ( A.posR == -1 )
res.posR = posR;
else
res.posR = A.posR;
res.count = count + A.count;
if ( count & 1 )
{
if ( posR != -1 && A.posL != -1 )
res.legalL[0] = legalL[0] && minval[posR] && A.legalL[1];
else
res.legalL[0] = legalL[0];
res.legalL[1] = legalL[1] && A.legalL[0];
}
else
{
res.legalL[0] = legalL[0] && A.legalL[0];
if ( posR != -1 && A.posL != -1 )
res.legalL[1] = legalL[1] && minval[posR] && A.legalL[1];
else
res.legalL[1] = legalL[1] || A.legalL[1];
}
if ( A.count & 1 )
{
if ( posR != -1 && A.posL != -1 )
res.legalR[0] = A.legalR[0] && minval[posR] && legalR[1];
else
res.legalR[0] = A.legalR[0];
res.legalR[1] = A.legalR[1] && legalR[0];
}
else
{
res.legalR[0] = A.legalR[0] && legalR[0];
if ( posR != -1 && A.posL != -1 )
res.legalR[1] = A.legalR[1] && minval[posR] && legalR[1];
else
res.legalR[1] = A.legalR[1] || legalR[1];
}
return res;
}
};
struct Segment_tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
Data tree[max1 * 4 + 5];
void Build ( int now, int L, int R )
{
if ( L == R )
{
if ( !( a[L] & 1 ) )
{
tree[now].sum = 1;
tree[now].countL[0][0] = 1;
tree[now].countL[0][1] = 0;
tree[now].countL[1][0] = 0;
tree[now].countL[1][1] = 0;
tree[now].countR[0][0] = 1;
tree[now].countR[0][1] = 0;
tree[now].countR[1][0] = 0;
tree[now].countR[1][1] = 0;
tree[now].count = 0;
tree[now].posL = -1;
tree[now].posR = -1;
tree[now].legalL[0] = true;
tree[now].legalL[1] = false;
tree[now].legalR[0] = true;
tree[now].legalR[1] = false;
}
else
{
tree[now].sum = 0;
tree[now].countL[0][0] = 0;
tree[now].countL[0][1] = 1;
tree[now].countL[1][0] = 1;
tree[now].countL[1][1] = 0;
tree[now].countR[0][0] = 0;
tree[now].countR[0][1] = 1;
tree[now].countR[1][0] = 1;
tree[now].countR[1][1] = 0;
tree[now].count = 1;
tree[now].posL = L;
tree[now].posR = L;
tree[now].legalL[0] = true;
tree[now].legalL[1] = true;
tree[now].legalR[0] = true;
tree[now].legalR[1] = true;
}
return;
}
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
tree[now] = tree[lson(now)] + tree[rson(now)];
return;
}
Data Query ( int now, int L, int R, int ql, int qr )
{
if ( L >= ql && R <= qr )
return tree[now];
int mid = L + R >> 1;
if ( qr <= mid )
return Query(lson(now), L, mid, ql, qr);
else if ( ql > mid )
return Query(rson(now), mid + 1, R, ql, qr);
return Query(lson(now), L, mid, ql, qr) + Query(rson(now), mid + 1, R, ql, qr);
}
}Tree;
int main ()
{
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d%d", &n, &q);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
minval[0] = inf;
int now = 0;
for ( int i = 1; i <= n; i ++ )
{
if ( a[i] & 1 )
minval[i] = inf, now = i;
else
minval[now] = min(minval[now], a[i]);
}
Tree.Build(1, 1, n);
int L, R; Data d;
while ( q -- )
{
scanf("%d%d", &L, &R);
d = Tree.Query(1, 1, n, L, R);
printf("%lld\n", d.sum);
}
return 0;
}
T2 B20
考虑到 \(l_1,r_1\) 是随机的，我们将询问按照 \(l_1\) 升序排序，发现 \(r_1\) 的最长上升子序列的期望长度是 \(O(\sqrt{q})\) （不知道如何发现的），也就是说我们可以将询问划分为 \(O(\sqrt{q})\) 组满足嵌套关系的询问，对于每组询问，由于指针单调移动，因此可以用吉司机线段树暴力维护，复杂度显然是 \(O(n\sqrt{q}\log n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
const int max1 = 15000, max2 = 1e5;
const int inf = 0x3f3f3f3f;
int n, m, q, a[max1 + 5];
struct Option
{
int id, L, R, x;
bool operator < ( const Option &A ) const
{ return x < A.x; }
}opt[max1 + 5];
struct Question
{
int id, L1, R1, L2, R2;
bool operator < ( const Question &A ) const
{ return L1 < A.L1; }
}qus[max2 + 5];
int suffix[max2 + 5]; bool vis[max2 + 5];
long long ans[max2 + 5];
multimap <int, int> Map;
struct Data
{
int max_val, cmax_val, count;
Data () {}
Data ( int __max_val, int __cmax_val, int __count )
{ max_val = __max_val, cmax_val = __cmax_val, count = __count; }
Data operator + ( const Data &A ) const
{
if ( max_val == A.max_val )
return Data(max_val, max(cmax_val, A.cmax_val), count + A.count);
else if ( max_val > A.max_val )
return Data(max_val, max(cmax_val, A.max_val), count);
return Data(A.max_val, max(max_val, A.cmax_val), A.count);
}
};
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
struct Struct_Segment_Tree
{ long long sum; Data d; int tag; } tree[max1 * 4 + 5];
void Push_Up ( int now )
{
tree[now].sum = tree[lson(now)].sum + tree[rson(now)].sum;
tree[now].d = tree[lson(now)].d + tree[rson(now)].d;
return;
}
void Update ( int now, int x )
{
if ( tree[now].d.max_val <= x )
return;
if ( tree[now].d.cmax_val < x )
{
tree[now].sum -= 1LL * tree[now].d.count * tree[now].d.max_val;
tree[now].d.max_val = x;
tree[now].sum += 1LL * tree[now].d.count * tree[now].d.max_val;
tree[now].tag = x;
}
else
{
Update(lson(now), x);
Update(rson(now), x);
Push_Up(now);
}
return;
}
void Push_Down ( int now )
{
if ( tree[now].tag != inf )
{
Update(lson(now), tree[now].tag);
Update(rson(now), tree[now].tag);
tree[now].tag = inf;
}
return;
}
void Build ( int now, int L, int R )
{
tree[now].tag = inf;
if ( L == R )
{
tree[now].sum = a[L];
tree[now].d.max_val = a[L];
tree[now].d.count = 1;
tree[now].d.cmax_val = -inf;
return;
}
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
Push_Up(now);
return;
}
void Insert ( int now, int L, int R, int ql, int qr, int x )
{
if ( tree[now].d.max_val <= x )
return;
if ( L >= ql && R <= qr )
return Update(now, x);
Push_Down(now);
int mid = L + R >> 1;
if ( ql <= mid )
Insert(lson(now), L, mid, ql, qr, x);
if ( qr > mid )
Insert(rson(now), mid + 1, R, ql, qr, x);
Push_Up(now);
return;
}
long long Query ( int now, int L, int R, int ql, int qr )
{
if ( L >= ql && R <= qr )
return tree[now].sum;
Push_Down(now);
int mid = L + R >> 1;
long long ans = 0;
if ( ql <= mid )
ans += Query(lson(now), L, mid, ql, qr);
if ( qr > mid )
ans += Query(rson(now), mid + 1, R, ql, qr);
return ans;
}
}Tree;
int main ()
{
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
for ( int i = 1; i <= m; i ++ )
scanf("%d%d%d", &opt[i].L, &opt[i].R, &opt[i].x), opt[i].id = i;
for ( int i = 1; i <= q; i ++ )
scanf("%d%d%d%d", &qus[i].L1, &qus[i].R1, &qus[i].L2, &qus[i].R2), qus[i].id = i;
sort(qus + 1, qus + 1 + q);
for ( int i = 1; i <= q; i ++ )
{
auto it = Map.lower_bound(qus[i].R1);
if ( it != Map.end() )
suffix[i] = it -> second, Map.erase(it);
Map.insert(make_pair(qus[i].R1, i));
}
int p = 0;
for ( int i = q; i >= 1; i -- )
{
if ( !vis[i] )
{
++p;
Tree.Build(1, 1, n);
int L = qus[i].L1, R = qus[i].L1 - 1;
for ( int k = i; k; k = suffix[k] )
{
while ( L > qus[k].L1 )
--L, Tree.Insert(1, 1, n, opt[L].L, opt[L].R, opt[L].x);
while ( R < qus[k].R1 )
++R, Tree.Insert(1, 1, n, opt[R].L, opt[R].R, opt[R].x);
vis[k] = true;
ans[qus[k].id] = Tree.Query(1, 1, n, qus[k].L2, qus[k].R2);
}
}
}
cerr << p << endl;
for ( int i = 1; i <= q; i ++ )
printf("%lld\n", ans[i]);
return 0;
}
T3 Chen 嘉然
多项式好恐怖。
容易发现答案可以表示为 \([x^m]\prod_i(1+xy^{\{a_i\}})\) 的形式，其中 \(x\) 为和卷积， \(y\) 为异或卷积，考虑对 \(f(y)\) 这个多项式进行 FWT ，也就是考虑求解 \(\operatorname{FWT}(1+xy^{\{a_i\}})\) ，由于异或卷积在 \(\operatorname{FWT}\) 中的计算方式为 \(fwt_i=\sum_{(i\operatorname{and}k)\operatorname{mod}2=0}f_k-\sum_{(i\operatorname{and}k)\operatorname{mod}2=1}f_k\) ，因此 FWT 后的数组每个位置只有 \(1-x\) 和 \(1+x\) 两种可能。所有 FWT 数组对应位置求和得到数组 \(b\) ，设这个位置存在 \(A\) 个 \(1-x\) ， \(B\) 个 \(1+x\) ，显然有 \(B-A=b_i,A+B=n\) ，因此考虑更快的得到数组 \(b\) ，由于 FWT 的过程是线性变换，因此可以根据分配律更快地求解，具体的记录 \(b_i\) 表示 \(i\) 权值的出现次数，对 \(b\) 进行 FWT 可以得到每个位置的 \(B-A\) 。
因此每个位置 FWT 之后的值实际上为 \([x^m](1+x)^c(1-x)^{n-c}\) ，简单推导：
\[\begin{aligned} [x^m](1+x)^c(1-x)^{n-c} &=\sum_i\binom{c}{i}\binom{n-c}{m-i}(-1)^{m-i}\\ &=c!(n-c)!\sum_i\tfrac{(-1)^{m-i}}{i!(m-i)!}\times\tfrac{1}{(c-i)!(n-m-(c-i))!} \end{aligned} \]很容易用 NTT 求解，总复杂度 \(O(n\log n)\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1 << 17;
const int mod = 998244353, gmod = 3;
int n, m, lim, a[max1 + 5], b[max1 + 5];
int inv[max1 + 5], fac[max1 + 5], ifac[max1 + 5];
int bit, total, rev[max1 * 2 + 5], f[max1 * 2 + 5], g[max1 * 2 + 5];
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
void Iterative_NTT ( int A[], int type, int len )
{
for ( int i = 0; i < len; i ++ )
if ( i < rev[i] )
swap(A[i], A[rev[i]]);
for ( int mid = 2; mid <= len; mid <<= 1 )
{
int wn = Quick_Power(gmod, ( mod - 1 ) / mid);
if ( type == -1 )
wn = Quick_Power(wn, mod - 2);
for ( int i = 0; i < len; i += mid )
{
int w = 1;
for ( int k = 0; k < mid >> 1; k ++ )
{
int x = A[i + k], y = 1LL * w * A[i + ( mid >> 1 ) + k] % mod;
A[i + k] = ( x + y ) % mod;
A[i + ( mid >> 1 ) + k] = ( x - y + mod ) % mod;
w = 1LL * w * wn % mod;
}
}
}
return;
}
int main ()
{
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%d%d%d", &n, &m, &lim);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]), ++b[a[i]];
for ( int i = 0; i < __lg(lim); i ++ )
{
for ( int j = 0; j < lim; j += 1 << i + 1 )
{
for ( int k = 0; k < 1 << i; k ++ )
{
int x = b[j + k], y = b[( 1 << i ) + j + k];
b[j + k] = x + y;
b[( 1 << i ) + j + k] = x - y;
}
}
}
inv[1] = 1;
for ( int i = 2; i <= n; i ++ )
inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
fac[0] = 1, ifac[0] = inv[1];
for ( int i = 1; i <= n; i ++ )
fac[i] = 1LL * fac[i - 1] * i % mod,
ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
bit = __lg(n) + 1;
total = 1 << bit;
rev[0] = 0;
for ( int i = 1; i < total; i ++ )
rev[i] = rev[i >> 1] >> 1 | ( i & 1 ) << bit - 1;
for ( int i = 0; i < total; i ++ )
f[i] = g[i] = 0;
for ( int i = 0; i <= m; i ++ )
{
if ( m - i & 1 )
f[i] = 1LL * ( mod - 1 ) * ifac[i] % mod * ifac[m - i] % mod;
else
f[i] = 1LL * ifac[i] * ifac[m - i] % mod;
}
for ( int i = 0; i <= n - m; i ++ )
g[i] = 1LL * ifac[i] * ifac[n - m - i] % mod;
Iterative_NTT(f, 1, total);
Iterative_NTT(g, 1, total);
for ( int i = 0; i < total; i ++ )
f[i] = 1LL * f[i] * g[i] % mod;
Iterative_NTT(f, -1, total);
int P = Quick_Power(total, mod - 2);
for ( int i = 0; i < total; i ++ )
f[i] = 1LL * f[i] * P % mod;
for ( int i = 0; i <= n; i ++ )
f[i] = 1LL * f[i] * fac[i] % mod * fac[n - i] % mod;
for ( int i = 0; i < lim; i ++ )
b[i] = f[n + b[i] >> 1];
for ( int i = 0; i < __lg(lim); i ++ )
{
for ( int j = 0; j < lim; j += 1 << i + 1 )
{
for ( int k = 0; k < 1 << i; k ++ )
{
int x = b[j + k], y = b[( 1 << i ) + j + k];
b[j + k] = 1LL * ( x + y ) * ( mod + 1 >> 1 ) % mod;
b[( 1 << i ) + j + k] = 1LL * ( x - y + mod ) * ( mod + 1 >> 1 ) % mod;
}
}
}
for ( int i = 0; i < lim; i ++ )
printf("%d ", b[i]);
printf("\n");
return 0;
}