P3531 [POI2012]LIT-Letters

本文主要是介绍P3531 [POI2012]LIT-Letters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求逆序对怎么能少了线段树呢.
建一棵权值线段树,倒着将每个数放入,每放入一个数之前先查询这颗线段树内有多少比它小的数,最后统计起来(注意用long long),废话不多说,直接上代码.

#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
#define sing(i,first,last) for(int i=first;i>=last;--i)
#define Lson now*2
#define Rson now*2+1
#define Middle (left+right)/2
#define Left Lson,left,Middle
#define Right Rson,Middle+1,right
using namespace std;
const int maxN=1e6+7;
int N,M;
char A[maxN],B[maxN];
int tree[maxN*4];
void PushUp(int now)//合并
{tree[now]=tree[Lson]+tree[Rson];
}
void Build(int now=1,int left=1,int right=N)//建树,没什么用
{if(left==right){tree[now]=0;return;}Build(Left);Build(Right);PushUp(now);
}
void UpData(int num,int now=1,int left=1,int right=N)//单点修改
{if(num<left||num>right)return;//不在范围内则退出if(left==right){tree[now]++;//叶节点时加一return;}UpData(num,Left);//修改左子树UpData(num,Right);//修改右子树PushUp(now);//合并
}
int Query(int num,int now=1,int left=1,int right=N)
{if(left>=num)return 0;//如果最小值也比查询的值也要大(相等)了就退出if(right<num)return tree[now];//如果最大值也比它小就直接返回return Query(num,Left)+Query(num,Right);//左右子树的值相加
}
int arr[26][maxN];
int cnt[26];
int brr[maxN];
int main()
{scanf("%d%s%s",&N,A,B);rap(i,0,N-1)arr[A[i]-'A'][++cnt[A[i]-'A']]=i+1;//因为相同时两个数自然是不会交换的,可见这是一个稳定的排序,所以记录下每个字母的位置依次带入b数组就可以了rap(i,0,25)cnt[i]=0;rap(i,0,N-1){brr[i+1]=arr[B[i]-'A'][++cnt[B[i]-'A']];}long long answer=0;sing(i,N,1){answer+=Query(brr[i]);//每个数的逆序对个数相加UpData(brr[i]);//加入这个数}printf("%lld",answer);//输出answerreturn 0;
}

这篇关于P3531 [POI2012]LIT-Letters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---