BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)
2018-07-12 07:32:49来源:博客园 阅读 ()
Submit: 6912 Solved: 2438
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1
5
3
4
2
5
1
4
2
Sample Output
2
2
1
样例解释
(1,5,3,4,2)?(1,3,4,2)?(3,4,2)?(3,2)?(3)。
HINT
Source
这题已知有三种做法:
1、主席树+树状数组
2、树套树随便套
3、cdq分治
用cdq分治的话有一种非常巧妙的思路:先时间倒流,那么每次询问就转化成了求逆序对的个数
其实也不用。。
我们考虑一个数删除之后会对答案产生怎样的贡献
设当前删除了第$i$个元素,那么在$1 - i$中比它大的都要减去
在$(i + 1) - N$中比他小的都要减去
这样的话直接正着循环一遍再倒着循环一遍就行了。
用树状数组求逆序对
代码抄借鉴的candy大佬,写的非常妙
#include<cstdio> #include<vector> #include<algorithm> #define LL long long using namespace std; const int MAXN = 400001, INF = 1e9 + 10; inline int read() { 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++) if(Q[i].t <= mid) Add(Q[i].val, Q[i].type); 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--) if(Q[i].t <= mid) Add(Q[i].val, Q[i].type); 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 N = read(); M = read(); 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++) { int x = read(); 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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:洛谷P1762 偶数(找规律)
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- STL之vector 2020-04-06
- 递归函数使用动态数组遇到的问题 2020-03-26
- 异常处理、动态内存申请在不同编译器之间的表现差异 2020-03-23
- 动态规划:最大子串和 2020-01-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash