【日常小测】回转寿司

Code

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

const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10;

int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];

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 void get_element(int w) {
if (opr[w].empty()) {
return;
}
priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end());
for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
if (arr[i] > heap.top()) {
heap.push(arr[i]);
arr[i] = heap.top();
heap.pop();
}
}
opr[w].clear();
}

inline int modify_element(int w, int s, int t, int v) {
get_element(w);
int tmp = -1;
for (int i = s; i <= t; i++) {
if (v < arr[i]) {
tmp = arr[i];
swap(v, arr[i]);
}
}
val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
return v;
}

inline int modify_block(int w, int v) {
val[w].push(v);
int ret = val[w].top();
val[w].pop();
if (v != ret) {
opr[w].push_back(v);
}
return ret;
}

inline int solve(int s, int t, int v) {
int ss = s / S, st = t / S;
v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
if (ss != st) {
for (int i = ss + 1; i < st; i++) {
v = modify_block(i, v);
}
v = modify_element(st, st * S, t, v);
}
return v;
}

int main() {
sn = n / S;
for (int i = 1; i <= n; i++) {
}
for (int i = 0; i <= sn; i++) {
val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
}
for (int tt = 1; tt <= m; tt++) {
if (s <= t) {
v = solve(s, t, v);
} else {
v = solve(s, n, v);
v = solve(1, t, v);
}
printf("%d\n", v);
}
return 0;
}


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

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;
}


【BZOJ 3509】[CodeChef] COUNTARI

解题报告

XeHoTh似乎用一份巨强暴力，卡到了BZOJ和CC的Rank 1

Code

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

const int M = 70009;
const int N = 100009;
const int T = 15;
const int L = 1 << T + 1;
const double EPS = 0.5;
const double PI = acos(-1);

int n,S,ed,arr[N],tot[M],pos[M];
struct COMPLEX{
double a,b;
inline COMPLEX() {}
inline COMPLEX(double x, double y):a(x),b(y) {}
inline COMPLEX operator - (const COMPLEX &B) {return COMPLEX(a-B.a,b-B.b);}
inline COMPLEX operator + (const COMPLEX &B) {return COMPLEX(a+B.a,b+B.b);}
inline COMPLEX operator * (const COMPLEX &B) {return COMPLEX(a*B.a-b*B.b,a*B.b+b*B.a);}
}a1[M],a2[M],bas(1,0);
LL vout,cnt[M];

char c=getchar(); int ret=0,f=1;
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;
}

inline void FFT(COMPLEX *a, int T = 1) {
for (int i=0;i<L;i++) if (pos[i]<i) swap(a[pos[i]],a[i]);
for (int l=2;l<=L;l<<=1) {
COMPLEX wn(cos(2*PI/l),sin(2*PI/l)*T),w(1,0);
for (int i=0;i<L;i+=l,w=bas) {
for (int j=i;j<(i+(l>>1));j++,w=w*wn) {
COMPLEX tmp = w * a[j+(l>>1)];
a[j+(l>>1)] = a[j] - tmp;
a[j] = a[j] + tmp;
}
}
}
}

int main() {
n = read(); S = 4000;
for (int i=1;i<=n;i++) arr[i] = read();
for (int i=1;i<L;i++) pos[i] = (pos[i>>1]>>1)|((i&1)<<T);
for (int i=S+1;i+S<=n;i+=S) {
memset(a1,0,sizeof(a1));
memset(a2,0,sizeof(a2));
for (int j=1;j<i;j++) a1[arr[j]] = a1[arr[j]] + bas;
for (int j=i+S;j<=n;j++) a2[arr[j]] = a2[arr[j]] + bas;
FFT(a1); FFT(a2);
for (int j=0;j<L;j++) a1[j] = a1[j] * a2[j];
FFT(a1, -1);
for (int j=0;j<L;j++) cnt[j] = a1[j].a / L + EPS;
for (int j=i;j<i+S;j++) vout += cnt[arr[j]<<1];
}
for (int i=1,t;i<=n;i+=S) {
ed = max(ed, i);
for (int j=i,lim=min(n+1,i+S);j<lim;j++) {
for (int k=j+1;k<lim;k++) {
t = (arr[j] << 1) - arr[k];
vout += t<M&&t>0? tot[t]: 0;
}
tot[arr[j]]++;
}
}
memset(tot,0,sizeof(tot));
for (int i=ed,t;i>0;i-=S) {
for (int j=min(n,i+S-1);j>=i;j--) {
for (int k=j-1;k>=i;k--) {
t = (arr[j] << 1) - arr[k];
vout += t<M&&t>0? tot[t]: 0;
}
}
for (int j=min(n,i+S-1);j>=i;j--) tot[arr[j]]++;
}
printf("%lld\n",vout);
return 0;
}


【BZOJ 2821】作诗(Poetize)

解题报告

$f[i][j]$ 表示第i个大块到第j个大块的答案