题目大意是在能够改变两个数的位置的情况下计算逆序对数

这因为是动态记录逆序对

本来单纯逆序对只要用树状数组计算即可,但这里因为更新,所以利用TReap树的删点和增加点来进行更新

大致是把每个树状数组所管理的点都放在对应的Treap树下,

这样x-=lowbit(x)下来,正好访问到是所有比他小范围下的点了

然后根据每棵访问到的Treap树有多少个节点是比当前值小的即可

每次交换ai , aj , (i<j)只要考虑(i,j)范围内比ai大的数,比aj小的数,然后加加减减即可

如果ai!=aj也是要加减1

 #include <bits/stdc++.h>

 using namespace std;
#define N 20005 struct Node{
int l , r , val , sz , pri , cnt;
//cnt表示当前位置相同的数有多少个,pri表示优先级,sz表示这棵子树所含有的节点总个数
Node(){
l = r = ;
cnt = sz = , pri = rand();
val = ;
}
Node(int v){
Node();
val = v;
}
};
#define ls node[x].l
#define rs node[x].r
namespace Treap{
int tot;//Treap Node节点的总个数
int A[N];//有n棵treap树,A[]表示每棵treap树的起始位置
Node node[N*];
void init(){
node[] = Node();
node[].cnt = node[].sz = ;
memset(A , , sizeof(A));
tot = ;
}
int newNode(int v){
++tot;
node[tot].cnt = node[tot].sz = ;
node[tot].l = node[tot].r = ;
node[tot].pri = rand();
node[tot].val = v;
return tot;
}
void push_up(int x) {
// cout<<"here: "<<x<<" "<<ls<<" "<<rs<<endl;
if(x>)
node[x].sz = node[ls].sz+node[rs].sz+node[x].cnt;
}
void rotL(int &x){
int y = rs;
rs = node[y].l;
node[y].l = x; push_up(x);
push_up(y);
x = y;
}
void rotR(int &x){
int y = ls;
ls = node[y].r;
node[y].r = x; push_up(x);
push_up(y);
x = y;
}
void insert(int &x , int v){
// cout<<x<<" "<<v<<endl;
if(x == ) x = newNode(v);
else if(node[x].val>v){
insert(ls , v);
if(node[ls].pri>node[x].pri) rotR(x);
}
else if(node[x].val<v){
insert(rs , v);
if(node[rs].pri>node[x].pri) rotL(x);
}
else node[x].cnt++;
push_up(x);
// cout<<x<<" "<<v<<" "<<"endd"<<endl;
}
void erase(int &x , int v){
if(x == ) return ;
else if(v<node[x].val) erase(ls , v);
else if(v>node[x].val) erase(rs , v);
else {
node[x].cnt--;
if(node[x].cnt<=){
if(ls==&&rs==) x = ;
else if(ls == ) x = rs;
else if(rs == ) x = ls;
else{
if(node[ls].pri <node[rs].pri) rotL(x),erase(ls,v);
else rotR(x) , erase(rs , v);
}
}
}
push_up(x);
}
int getCnt(int x , int v){//从x号节点出发找到对应的子树下小于等于v的值的个数
if(x == ) return ;
int ans = ;
if(node[x].val>v) ans = getCnt(ls , v);
else if(node[x].val<v) ans = node[x].cnt+node[ls].sz+getCnt(rs , v);
else ans = node[x].cnt+node[ls].sz;
return ans;
}
}
int n , m , h[N] , a[N] , tot;
//树状数组部分
#define lowbit(x) x&(-x)
void Add(int id , int v)
{
for(int x=id ; x<=n ; x+=lowbit(x)){
Treap::insert(Treap::A[x] , v);
}
}
void Erase(int id , int v)
{
for(int x=id ; x<=n ; x+=lowbit(x)){
Treap::erase(Treap::A[x] , v);
}
}
int getSum(int p , int v)//cal 1~p区间内小于等于v的值的个数
{
int sum = ;
for(int x=p ; x> ; x-=lowbit(x)){
sum+=Treap::getCnt(Treap::A[x] , v);
}
return sum;
}
int getSumMin(int p , int v)//cal 1~p区间内小于v的值的个数
{
v--;//important保证等于的情况被排除
return getSum(p , v);
} int main()
{
// freopen("a.in" , "r" , stdin);
scanf("%d" , &n);
for(int i= ; i<=n ; i++){
scanf("%d" , &h[i]);
a[i] = h[i];
}
sort(a+ , a+n+);
tot = unique(a+ , a+n+)-(a+);
Treap::init();
int sum = ;
for(int i= ; i<=n ; i++){
h[i] = lower_bound(a+ , a+tot+ , h[i])-a;
Add(i , h[i]);
sum+=i--getSum(i- , h[i]);
}
printf("%d\n" , sum); scanf("%d" , &m);
while(m--){
// for(int i=1 ; i<=n ; i++)
// cout<<h[i]<<" ";
// cout<<endl;
int ai , bi;
scanf("%d%d" , &ai , &bi);
if(ai>bi) swap(ai , bi);
if(h[ai]<h[bi]) sum++;
else if(h[ai]>h[bi]) sum--;
else{
printf("%d\n" , sum);
continue;
}
int add = ;
if(bi-ai>){
add += getSumMin(bi- , h[bi])-getSumMin(ai , h[bi]);
add -= (bi-ai-)-(getSum(bi- , h[bi])-getSum(ai , h[bi]));
add += (bi-ai-)-(getSum(bi- , h[ai])-getSum(ai , h[ai]));
add -= getSumMin(bi- , h[ai])-getSumMin(ai , h[ai]);
} sum += add; Erase(ai , h[ai]);
Erase(bi , h[bi]);
Add(ai , h[bi]);
Add(bi , h[ai]);
swap(h[ai] , h[bi]);
printf("%d\n" , sum);
}
return ;
}

最新文章

  1. peer not authenticated的终极解决方案
  2. Boost学习笔记(一) 什么是Boost
  3. thinkphp 3.2.3 连接sql server 2014 WAMPSERVER环境包
  4. mysql 事务隔离级别
  5. Python多个版本安装!
  6. hdu 1212 Big Number
  7. Ant编译和部署java web项目
  8. ios 微信细节
  9. SVN理解
  10. Android 获取天气预报
  11. java时间格式大全
  12. android中解析文件的三种方式
  13. jQuery复习:第四章
  14. VMware虚拟机安装教程
  15. Codeforces 1101G(线性基)
  16. Java实现post和get请求
  17. css flex布局,小程序flex布局,垂直居中完美解决
  18. leedcode算法解题思路
  19. Spring AOP 切面编程实战Demo项目
  20. chrome 调试进入 paused in debugger 状态解决办法

热门文章

  1. ElasticSearch5中文分词(IK)
  2. plist文件
  3. Strus2第一次课:dom4j操作xml
  4. (原创)vim配色------水果色,不伤眼。
  5. Oralce 账户被锁后的解决办法
  6. Git撤销操作
  7. 转!!windows记事本保存“联通” 编码问题
  8. javascript学习内容--object.style.display=&quot;value&quot; value值为“”none“隐藏”或 &quot;block&quot;显示
  9. Failed: error processing document #281: unexpected EOF,往MongoDB当中插入json文件时出现的错误。
  10. Android 写模块化代码注意事项