BZOJ3295动态逆序对
2024-08-27 02:07:58
一道比较傻的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('\n');
}
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('\n');
}
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,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
最新文章
- 并发读写缓存实现机制(一):为什么ConcurrentHashMap可以这么快?
- Linux中的工作管理(Job Control )
- 爱上MVC~AuthorizeAttribute验证不通过如何停止当前上下文
- BZOJ3165 : [Heoi2013]Segment
- .Net码农学Android---前言
- UVa 1599 (字典序最小的最短路) Ideal Path
- Java学习----Math函数
- Log4j简单配置
- mysql相关日志汇总
- [Windows Phone]解锁、注册Windows Phone实体手机为开发机(Windows 8)
- .NET 类库研究
- 【IE6的疯狂之九】li在IE中底部空行的BUG
- C++中使用const修饰指针
- .Net MVC5异步请求Entity Framework 无限循环解决方法
- redis 设置
- EF CodeFirst系列(7)---FluentApi配置存储过程
- java多线程之堵塞的应用
- Linux下vim基本操作和清空文件内容的常用方法
- 高性能JSON框架之FastJson的简单使用
- laravel配置路由出现404