# BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 6912  Solved: 2438

[Submit][Status][Discuss]

## Input

N<=100000 M<=50000

## Sample Input

5 4 1 5 3 4 2 5 1 4 2

## Sample Output

5 2 2 1 样例解释 (1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

## Source

1、主席树+树状数组

2、树套树随便套

3、cdq分治

#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN = 400001, INF = 1e9 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
struct Query {
int t, x, val, type, id;
bool operator < (const Query &rhs) const {
return x == rhs.x ? val < rhs.val : x < rhs.x;
}
}Q[MAXN], Tp[MAXN];
int N, M, a[MAXN], pos[MAXN], tim;
LL ans[MAXN];

#define lb(x) (x & -x)
int T[MAXN];
void Add(int pos, int val) {for(int i = pos; i <= N; i += lb(i)) T[i] += val;}
int Sum(int pos) {int ans = 0; for(int i = pos; i >= 1; i -= lb(i)) ans += T[i]; return ans;}

void CDQ(int l, int r) {
if(l == r) return;
int mid = l + r >> 1;
for(int i = l; i <= r; i++)
else ans[Q[i].id] += Q[i].type * (Sum(N) - Sum(Q[i].val));
for(int i = l; i <= r; i++) if(Q[i].t <= mid) Add(Q[i].val, -Q[i].type);

for(int i = r; i >= l; i--)
else ans[Q[i].id] += Q[i].type * (Sum(Q[i].val - 1));
for(int i = l; i <= r; i++)if(Q[i].t <= mid) Add(Q[i].val, -Q[i].type);

int p1 = l, p2 = mid + 1;
for(int i = l; i <= r; i++)
if(Q[i].t <= mid) Tp[p1++] = Q[i];
else Tp[p2++] = Q[i];
for(int i = l; i <= r; i++) Q[i] = Tp[i];
CDQ(l, mid); CDQ(mid + 1, r);
}
int main() {
#ifdef WIN32
//freopen("a.in", "r", stdin);
#endif
for(int i = 1; i <= N; i++) {
a[i] = read(); pos[a[i]] = i ;
Q[++tim] = (Query) {tim, i, a[i], 1, 0};
}
for(int i = 1; i <= M; i++) {
Q[++tim] = (Query) {tim, pos[x], x, -1, i};
}
sort(Q + 1, Q + tim + 1);
CDQ(1, tim);
for(int i = 1; i <= M; i++) {
ans[i] += ans[i - 1];
printf("%lld\n", ans[i - 1]);
}
return 0;
}

1811 篇文章123 人订阅

0 条评论

## 相关文章

### Oozie分布式工作流——EL表达式

oozie支持使用EL（expression language）表达式。 基本的EL常量 KB MB GB TB PB 基本EL函数 string fir...

27780

### LeetCode 473 Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchstic...

12230

14820

### [6] - 类和对象之进阶（二）

Scala 中的可见性非常灵活且复杂，这篇文章希望通过大量的示例来说清楚各种情况下的可见性是怎么样的。

7520

### Scalaz（56）－ scalaz-stream: fs2-安全运算，fs2 resource safety

fs2在处理异常及资源使用安全方面也有比较大的改善。fs2 Stream可以有几种方式自行引发异常：直接以函数式方式用fail来引发异常、在纯代码里隐式...

21350

### 反射基础之Field

java.lang.reflect.Field 类的方法可以查询字段的信息。比如：名字，类型，修饰符和注解。同样也有方法可以动态访问和修改字段的值。

16410

### fastjson详解

fastjson用于将Java Bean序列化为JSON字符串，也可以从JSON字符串反序列化到JavaBean。

94510

40350

6920

12160