专栏首页Zaqdt_ACM牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

题目链接:https://ac.nowcoder.com/acm/contest/308/D

       这道题说了只需要求逆序数的奇偶性,然后我们就要先确定一个概念,一个数列的逆序数为奇数的话就成为奇排列,如果是偶数就是偶排列,然后对于逆序数列有一个定理是交换任意两个数会使得奇偶性交换一次,也就是逆序数会从奇变偶或从偶变奇,所以这道题就变的简单了,我们首先求出1-n的逆序数,然后判断奇偶,然后对于每个查询操作都是判断查找的长度的奇偶性(因为如果是偶数的话,两两交换以后奇偶性不变),再判断k的奇偶性就好了。


AC代码:

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,pre[maxn];
map<int,int> ma;
 
int lowbit(int x){return x & (-x);}
 
void Update(int x){
  for(int i=x;i<=n;i+=lowbit(i)){
    ma[i] ++;
  }
}
 
int Query(int x){
  int ans = 0;
  for(int i=x;i>=1;i-=lowbit(i)){
    ans += ma[i];
  }
  return ans;
}
 
int main()
{
  while(~scanf("%d",&n)){
    ma.clear();
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++){
      scanf("%d",&pre[i]);
      // pre[i]++;
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
      Update(pre[i]);
      ans += (i - Query(pre[i])) % 2;
    }
    int m;
    scanf("%d",&m);
    while(m--){
      int l, r, k;
      scanf("%d%d%d",&l,&r,&k);
      ans += (r - l) % 2 * k % 2;
      printf("%d\n",ans % 2);
    }
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • NYOJ 116 士兵杀敌(二) (线段树+树状数组)

    题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=116

    Ch_Zaqdt
  • 牛客寒假算法基础集训营4 F. Applese的QQ群(二分+拓扑排序+dfs)

    题目链接:https://ac.nowcoder.com/acm/contest/330/F

    Ch_Zaqdt
  • C语言中一些不被熟知的特性

    限定词restricted用于限定一个指针(如名,告诉编译器该指针的内存访问在任何情况下都只能通过该指针进行,其余指向无效.如

    racaljk
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack

扫码关注云+社区

领取腾讯云代金券