PAT-T1027 Larry and Inversions （树状数组）
标签：eof 答案 versions ret ack namespace val 数组 memset
题意：
每次翻转一段区间，询问翻转区间后整个序列的逆序对数量。
题解：
每次翻转区间，那么翻转区间的答案就是整个序列的原始答案减去这个区间里逆序对的数量加上顺序对的数量。
统计逆序对和顺序对用树状数组做。
#includeusing namespace std;
const int maxn=1010;
int n;
int a[maxn];
int c[maxn];
int lowbit(int x) {
return x&-x;
}
void add (int x,int val) {
for (int i=x;ival;
}
int getsum (int x) {
int ans=0;
for (int i=x;i;i-=lowbit(i)) ans+=c[i];
return ans;
}
vectorint> ans;
int main () {
scanf("%d",&n);
for (int i=1;i"%d",a+i);
int wjm=0;
for (int i=1;i) {
wjm+=getsum(n)-getsum(a[i]);
add(a[i],1);
}
for (int i=1;i) {
memset(c,0,sizeof(c));
int sum=0;
int sum_=0;//顺序对数量
for (int j=i;j) {
sum+=getsum(n)-getsum(a[j]);
sum_+=getsum(a[j]);
//翻转一段区间，答案就是总的逆序对数量减去这个区间内的逆序对数量加上这个区间的顺序对数量
ans.push_back(wjm-sum+sum_);
add(a[j],1);
}
//
}
for (int i=0;i) {
if (i) printf(" ");
printf("%d",ans[i]);
}
}
PAT-T1027 Larry and Inversions （树状数组）
标签：eof 答案 versions ret ack namespace val 数组 memset
原文地址：https://www.cnblogs.com/zhanglichen/p/13357042.html
评论