一道比较傻的CDQ分治
CDQ: 主要用于解决三位偏序的问题
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
using namespace std;
inline long long read()
{
long long x = 0, flag = 1;
char c;
while(! isgraph(c = getchar()))
if(c == '-')
flag *= - 1;
while(isgraph(c))
x = x * 10 + c - '0', c = getchar();
return x * flag;
}
void println(long long x)
{
if(x < 0)
putchar('-'), x *= - 1;
if(x == 0)
putchar('0');
long long ans[10 + (1 << 4)], top = 0;
while(x)
ans[top ++] = x % 10, x /= 10;
for(; top; top --)
putchar(ans[top - 1] + '0');
putchar('
');
}
const long long MAXN = (long long)1e5 + (1 << 5);
struct spot
{
long long t, pos, w;
spot(){}
spot(long long t, long long pos, long long w): t(t), pos(pos), w(w){}
}a[MAXN], b[MAXN];
long long pos[MAXN];
long long operator <(spot x, spot y)
{
if(x.t != y.t)
return x.t < y.t;
return x.pos < y.pos;
}
long long n;
long long ans[MAXN];
long long tree[MAXN];
void modify(long long u, long long delta)
{
while(u <= n)
tree[u] += delta, u += (u & (-u));
}
long long query(long long u)
{
long long ret = 0;
while(u)
ret += tree[u], u -= (u & (- u));
return ret;
}
long long cmp(spot x, spot y)
{
return x.pos < y.pos;
}
void CDQ(long long L, long long R)
{
if(L + 1 >= R)
return;
long long top = 0;
long long mid = (L + R) >> 1;
for(long long i = L; i < mid; i ++)
b[top] = a[i], b[top ++].t = - 1;
for(long long i = mid; i < R; i ++)
b[top ++] = a[i];
sort(b, b + top, cmp);
long long cnt = 0;
for(long long i = 0; i < top; i ++)
{
if(b[i].t == - 1)
modify(b[i].w, 1), cnt ++;
else
ans[b[i].t] += query(n) - query(b[i].w);
}
for(long long i = 0; i < top; i ++)
if(b[i].t == - 1)
modify(b[i].w, - 1);
CDQ(L, mid);
CDQ(mid, R);
}
long long cmp2(spot x, spot y)
{
if(x.t != y.t)
return x.t < y.t;
return x.pos > y.pos;
}
long long cmp1(spot x, spot y)
{
return x.pos > y.pos;
}
void CDQ1(long long L, long long R)
{
if(L + 1 >= R)
return;
long long top = 0;
long long mid = (L + R) >> 1;
for(long long i = L; i < mid; i ++)
b[top] = a[i], b[top ++].t = - 1;
for(long long i = mid; i < R; i ++)
b[top ++] = a[i];
sort(b, b + top, cmp1);
long long cnt = 0;
for(long long i = 0; i < top; i ++)
{
if(b[i].t == - 1)
modify(b[i].w, 1), cnt ++;
else
ans[b[i].t] += query(b[i].w);
}
for(long long i = 0; i < top; i ++)
if(b[i].t == - 1)
modify(b[i].w, - 1);
CDQ1(L, mid);
CDQ1(mid, R);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("BZOJ3295.in", "r", stdin);
freopen("BZOJ3295.out", "w", stdout);
#endif
n = read();
long long m = read();
for(long long i = 0; i < n; i ++)
a[i].pos = i, a[i].w = read(), a[i].t = n - m, pos[a[i].w] = i;
for(long long i = 0; i < m; i ++)
a[pos[read()]].t = n - i;
sort(a, a + n);
memset(ans, 0, sizeof(ans));
memset(tree, 0, sizeof(tree));
CDQ(0, n);
sort(a, a + n, cmp2);
CDQ1(0, n);
for(long long i = n - m + 2; i <= n; i ++)
ans[i] += ans[i - 1];
for(long long i = n; i > n - m; i --)
println(ans[i]);
}
顺便, 承蒙YAY大神的指导, 学会了一个可以用来出数据的函数random_shuffle(int&, int&), 用于随机打乱区间中的元素. 附上对拍代码
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
using namespace std;
inline int read()
{
int x = 0, flag = 1;
char c;
while(! isgraph(c = getchar()))
if(c == '-')
flag *= - 1;
while(isgraph(c))
x = x * 10 + c - '0', c = getchar();
return x * flag;
}
void println(int x)
{
if(x < 0)
putchar('-'), x *= - 1;
if(x == 0)
putchar('0');
int ans[10 + (1 << 4)], top = 0;
while(x)
ans[top ++] = x % 10, x /= 10;
for(; top; top --)
putchar(ans[top - 1] + '0');
putchar('
');
}
const int maxn=1e5+10;
int a[maxn];
int main() {
freopen("bzoj3295.in","w",stdout);
srand(time(0));
int n=100000;
printf("%d %d
",n,n);
for (int i=1;i<=n;++i) a[i]=i;
random_shuffle(a+1,a+n+1);
for (int i=1;i<=n;++i) printf("%d ",a[i]);
puts("");
random_shuffle(a+1,a+n+1);
for (int i=1;i<=n;++i) printf("%d ",a[i]);
puts("");
}
对拍用的BAT
@echo off
:loop
mkd
BZOJ3295
ni
fc BZOJ3295.out ni.out
if not errorlevel 1 goto loop
pause