T = int(input()) for _ inrange(T): n = int(input()) a = list(map(int, input().split())) have0 = 0in a count_negative = sum([1for i in a if i < 0]) if count_negative % 2 == 1or have0: print('0') else: print('1\n1 0')
signedmain(){ kin >> T; while (T--) { kin >> n >> k >> d; for (int i = 1; i <= n; ++i) kin >> a[i]; for (int i = 1; i <= k; ++i) kin >> v[i]; int performDayMax = min(n * 2, d - 1); int equalZero = 0; for (int i = 1; i <= n; ++i) { a[i] -= i; if (a[i] == 0) equalZero++; } int ans = (d - 1) / 2 + equalZero; for (int passDay = 1; passDay <= performDayMax; ++passDay) { // Actual pass: passDay + 1 int vi = v[(passDay - 1) % k + 1]; for (int i = 1; i <= vi; ++i) { if (a[i] == 0) { a[i] = 1; --equalZero; } elseif (a[i] < 0) { if (++a[i] == 0) ++equalZero; } } int current = (d - passDay - 1) / 2 + equalZero; ans = max(ans, current); } kout << ans << '\n'; } return0; }
namespace nxd { int binarytr[N], _n; voidinit(int n){ _n = n; for (int i = 1; i <= n; ++i) binarytr[i] = 0; } voidadd(int u, int v){ for (; u <= _n; u += u & -u) binarytr[u] += v; } intquery(int u){ int res = 0; for (; u; u -= u & -u) res += binarytr[u]; return res; } int64 query(int n, int *a){ init(n); int64 res = 0; for (int i = n; i; --i) { res += query(a[i]); add(a[i] + 1, 1); } return res % P; } }
namespace supernxd { int binarytr[N * 2], _n, _k; voidinit(int n, int k){ _n = n * 2; _k = k; for (int i = 1; i <= _n; ++i) binarytr[i] = 0; } voidadd(int u, int v){ for (; u <= _n; u += u & -u) binarytr[u] += v; } intquery(int u){ int res = 0; for (; u; u -= u & -u) res += binarytr[u]; return res; } intquery(int l, int r){ returnquery(r) - query(l - 1); } int64 calc_offset(int64 offset){ if (offset < 0) { if (offset < -_k) return0; return (_k + offset) * (_k + offset + 1) / 2 % P; } else { if (offset > _k) return (int64)_k * _k % P; return ((int64)_k * _k - (_k - offset) * (_k - offset + 1) / 2) % P; } } int64 query(int n, int k, int *a){ init(n, k); int64 res = 0; for (int i = 1; i <= n; ++i) { // lower part int rig = a[i], lef = rig / 2, step = -1; while (lef < rig) { int count = query(lef + 1, rig); res += calc_offset(step) * count % P; rig = lef; lef = lef / 2; --step; } // upper part rig = a[i] * 2, lef = a[i], step = 1; while (lef < _n) { int count = query(lef + 1, min(rig, _n)); res += calc_offset(step) * count % P; lef = rig; rig = rig * 2; ++step; } // add add(a[i], 1); } return res % P; }
}
int p[N], q[N];
signedmain(){ kin >> T; while (T--) { kin >> n >> k; for (int i = 1; i <= n; ++i) kin >> p[i]; for (int i = 1; i <= k; ++i) kin >> q[i]; int64 ans = (nxd::query(k, q) * n + supernxd::query(n, k, p)) % P; kout << ans << '\n'; } return0; }