BZOJ2141&洛谷1975 排队 【线段树套treap】
题目
排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。
红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i<j且hi>hj的(i,j)数量。
幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。
输入格式
第一行为一个正整数n，表示小朋友的数量；
第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；
第三行为一个正整数m，表示交换操作的次数；
以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。
输出格式
输出文件共m+1行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。
输入样例
3
130 150 140
2
2 3
1 3
输出样例
1
0
3
提示
【样例说明】
未进行任何操作时，(2,3)满足条件；
操作1结束后，序列为130 140 150，不存在满足i<j且hi>hj的(i,j)对；
操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)。
对于15%的数据，n,m \le 15n,m≤15；
对于30%的数据，n,m \le 200n,m≤200；
在剩下的70%数据中：
存在15%的数据，h_ih
i
各不相同；
存在15%的数据，1^{10} \le h_i \le 1^{60}1
10
≤h
i
≤1
60
；
以上两类数据不存在交集。
对于100%的数据，1 \le m \le 2\times 10^31≤m≤2×10
3
，1 \le n \le 2 \times 10^41≤n≤2×10
4
，1 \le h_i \le 10^91≤h
i
≤10
9
，a_i \ne b_ia
i
≠b
i
，1 \le a_i,b_i \le n1≤a
i
,b
i
≤n。
题解
数据结构什么的查错真的是查得想死啊，，
不过A了就很舒服~~
蒟蒻没写过treap，今天一跃写了线段树套treap，感觉整个人要虚脱
嘴上AC还是不难：
先用离散化 + 树状数组算出初始的逆序对
之后没交换L和R，我们只需要考虑他们对答案带来的影响：
①L和R，若h[L]>h[R]，交换后逆序对会减少1；若h[L] < h[R]，交换后逆序对会增加1
②L和R与他们两边的元素的相对位置不变，只对(L,R)区间内产生影响，只要求出(L,R)区间内比h[L]和h[R]小和大的个数来更新答案即可
【一开始忘记判l>r WA了，后来发现一开始求逆序对时没考虑相等，又WA 。。QAQ】
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
#define lbt(u) (u & -u)
using namespace std;
const int maxn = 20005,maxm = 5000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
return out * flag;
}
int n,m,A[maxn],rt[4 * maxn];
int Siz,ls[maxm],rs[maxm],val[maxm],cnt[maxm],siz[maxm],rnd[maxm];
void pup(int u){
siz[u] = siz[ls[u]] + siz[rs[u]] + cnt[u];
}
void lturn(int& u){
int t = rs[u]; rs[u] = ls[t]; ls[t] = u;
pup(u); pup(t); u = t;
}
void rturn(int& u){
int t = ls[u]; ls[u] = rs[t]; rs[t] = u;
pup(u); pup(t); u = t;
}
void ins(int& u,int v){
if (!u) {
u = ++Siz; val[u] = v;
rnd[u] = rand(); siz[u] = cnt[u] = 1;
}
else if (val[u] > v) {
siz[u]++; ins(ls[u],v);
if (rnd[ls[u]] > rnd[u]) rturn(u);
}
else if (val[u] < v) {
siz[u]++; ins(rs[u],v);
if (rnd[rs[u]] > rnd[u]) lturn(u);
}
else cnt[u]++,siz[u]++;
}
void del(int &u,int v)
{
if(!u) return;
if(val[u] == v)
{
if(cnt[u] > 1) cnt[u]--,siz[u]--;
else if(ls[u] * rs[u] == 0) u = ls[u] + rs[u];
else if(rnd[ls[u]] > rnd[rs[u]]) rturn(u),del(u,v);
else lturn(u),del(u,v);
}
else if(v < val[u]) siz[u]--,del(ls[u],v);
else siz[u]--,del(rs[u],v);
}
int getpre(int r,int v){
int ans = 0,u = rt[r];
while (true){
if (!u) return ans;
else if (val[u] > v) u = ls[u];
else if (val[u] < v) ans += siz[ls[u]] + cnt[u],u = rs[u];
else return ans + siz[ls[u]];
}
}
int getpost(int r,int v){
int ans = 0,u = rt[r];
while (true){
if (!u) return ans;
else if (val[u] < v) u = rs[u];
else if (val[u] > v) ans += siz[rs[u]] + cnt[u],u = ls[u];
else return ans + siz[rs[u]];
}
}
void build(int u,int l,int r){
for (int i = l; i <= r; i++) ins(rt[u],A[i]);
if (l == r) return;
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
void modify(int u,int l,int r,int pos,int v){
del(rt[u],A[pos]); ins(rt[u],v);
if (l == r) return;
int mid = l + r >> 1;
if (mid >= pos) modify(u << 1,l,mid,pos,v);
else modify(u << 1 | 1,mid + 1,r,pos,v);
}
int Getpre(int u,int l,int r,int L,int R,int v){
if (l >= L && r <= R) return getpre(u,v);
int mid = l + r >> 1;
if (mid >= R) return Getpre(u << 1,l,mid,L,R,v);
else if (mid < L) return Getpre(u << 1 | 1,mid + 1,r,L,R,v);
else return Getpre(u << 1,l,mid,L,R,v) + Getpre(u << 1 | 1,mid + 1,r,L,R,v);
}
int Getpost(int u,int l,int r,int L,int R,int v){
if (l >= L && r <= R) return getpost(u,v);
int mid = l + r >> 1;
if (mid >= R) return Getpost(u << 1,l,mid,L,R,v);
else if (mid < L) return Getpost(u << 1 | 1,mid + 1,r,L,R,v);
else return Getpost(u << 1,l,mid,L,R,v) + Getpost(u << 1 | 1,mid + 1,r,L,R,v);
}
int b[maxn],s[maxn],Ans;
void add(int u){while (u <= n) s[u] ++,u += lbt(u);}
int query(int u){int tot = 0; while (u) tot += s[u],u -= lbt(u); return tot;}
int getn(int x){return lower_bound(b + 1,b + 1 + n,x) - b;}
int main(){
n = read(); int l,r;
REP(i,n) b[i] = A[i] = read();
sort(b + 1,b + 1 + n);
for (int i = n; i; i--){
int t = getn(A[i]);
Ans += query(t - 1);
add(t);
}
printf("%d\n",Ans);
build(1,1,n);
m = read();
while (m--){
l = read(); r = read();
if (l > r) swap(l,r);
if (l == r) {printf("%d\n",Ans); continue;}
if (A[l] < A[r]) Ans++;
if (A[l] > A[r]) Ans--;
if (l < r - 1){
Ans -= Getpre(1,1,n,l + 1,r - 1,A[l]);
Ans += Getpost(1,1,n,l + 1,r - 1,A[l]);
Ans -= Getpost(1,1,n,l + 1,r - 1,A[r]);
Ans += Getpre(1,1,n,l + 1,r - 1,A[r]);
}
modify(1,1,n,l,A[r]); modify(1,1,n,r,A[l]);
swap(A[l],A[r]);
printf("%d\n",Ans);
}
return 0;
}
最新文章
- SQL Server跨库查询
- 【LeetCode OJ】Validate Binary Search Tree
- Windows程序设再读笔记01-起步
- hdu 2094
- Git教程之删除文件(8)
- hadoop2.2基准测试
- Attributes(2): Displaying attributes for a class.(显示类属性)
- memcache memcached 区别
- java--照片和BYTE这些东西阵列
- mob分享
- IE11中navigator.userAgent的变化
- smarty模板基本语法
- C语言第九次博客作业--指针
- Linux 下执行本目录的可执行文件（命令）为什么需要在文件名前加“./”
- Excel 导入时如何下载模板信息（Java）
- PyCharm 使用Github管理Django项目
- C#Winform工具箱简介
- Java http请求工具类
- YII2中ActiveDataProvider与GridView的配合使用
- 《Linux内核分析》第二周笔记 操作系统是如何工作的