HDU5196--DZY Loves Inversions 树状数组逆序数

2023-07-31 23:48:24

题意查询给定[L, R]区间内逆序对数 ==k的子区间的个数。

我们只需要求出子区间小于等于k的个数和小于等于k-1的个数，然后相减就得出答案了。

对于

  1 #include <set>
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include <string>
  9 #include 
 10 #include 
 11 #include 
 12 #include 
 13 #include 
 14 using namespace std;
 15 typedef unsigned long long ull;
 16 typedef long long ll;
 17 const int inf = 0x3f3f3f3f;
 18 const double eps = 1e-8;
 19 const int maxn = 1e5+100;
 20 int n, q, tot, a[maxn];
 21 ll k, vec[maxn];
 22 int lowbit (int x)
 23 {
 24     return x &  -x;
 25 }
 26 ll arr[maxn];
 27 int M ;
 28 void modify(int x, int d)
 29 {
 30     while (x < M)
 31     {
 32         arr[x] += d;
 33         x += lowbit(x);
 34     }
 35 }
 36 ll sum(int x)
 37 {
 38     ll res = 0;
 39     while (x)
 40     {
 41         res += arr[x];
 42         x -= lowbit(x);
 43     }
 44     return res;
 45 }
 46 ll cnt[2][maxn];
 47 ll s[2][maxn];
 48 ll solve (int L, int R, ll x, int w)                 // 小于等于x的数量
 49 {
 50     if (x < 0)
 51         return 0;
 52     //int tmp = 0;
 53     int tmp = lower_bound(cnt[w]+L, cnt[w]+R+1, (ll)R) - cnt[w];
 54     while (tmp >= R+1)                           //  cnt数组中所有数都小于 R时，，得到的tmp是大于R+1的
 55         tmp--;
 56     while (cnt[w][tmp] > R && tmp >= L)
 57        tmp--;
 58     if (tmp < L)
 59         return (ll)R*(ll)(R-L+1) - (ll)(L+R)*(ll)(R-L+1)/2;
 60     return s[w][tmp] - s[w][L-1] - (ll)(R-tmp)*(ll)(R+tmp+1)/2+ (ll)(R-tmp)*(ll)R;
 61 }
 62 int main()
 63 {
 64     #ifndef ONLINE_JUDGE
 65         freopen("in.txt","r",stdin);
 66         freopen("out.txt", "w", stdout);
 67     #endif
 68     while (~scanf ("%d%d%I64d", &n, &q, &k))
 69     {
 70         M = n + 10;
 71         memset(arr, 0, sizeof (arr));
 72         memset(cnt, 0, sizeof (cnt));
 73         memset(s, 0, sizeof(s));
 74         for (int i = 0; i < n; i++)
 75         {
 76             scanf ("%I64d", vec+i);
 77             a[i] = vec[i];
 78         }
 79         sort (vec, vec+n);
 80         tot = unique(vec, vec+n) - vec;
 81         for (int i = 0; i < n; i++)
 82         {
 83             a[i] = lower_bound(vec, vec+tot, a[i]) - vec + 2;           //离散化
 84         }
 85         ll res = 0;
 86         //小于等于k
 87         for (int i = 0, j = 0; i < n; i++)
 88         {
 89             for ( ; j < n && res <= k; j++)
 90             {
 91                 res += (j - i) - sum(a[j]);
 92                 modify(a[j], 1);
 93             }
 94             if (res >= k)
 95                 cnt[1][i] = (res > k ? max(0,j -1-1): j-1) ;           // -1是因为 j先加了一下， 才跳出 循环的
 96             else
 97                 cnt[1][i] = j-1-1;
 98             s[1][i] = s[1][i-1] + cnt[1][i] - (i);
 99             modify(a[i], -1);
100             res -= sum(a[i]-1);
101         }
102 
103         //小于等于k-1
104         res = 0;
105         for (int i = 0, j = 0; i < n; i++)
106         {
107             for ( ; j < n && res <= (k-1); j++)
108             {
109                 res += (j-i) - sum(a[j]);
110                 modify(a[j], 1);
111             }
112             if (res >= k-1)
113                 cnt[0][i] = (res > (k-1) ? max(j-1-1,0) : j-1);
114             else
115                 cnt[0][i] = j-1-1;
116 
117             s[0][i] = s[0][i-1] + cnt[0][i] - (i);
118             modify(a[i], -1);
119             res -= sum(a[i]-1);
120         }
121         for (int i = 0; i < q; i++)
122         {
123             int u, v;
124             scanf ("%d%d", &u, &v);
125             u--, v--;
126             if (u > v)
127                 swap(u, v);
128             ll ans1 = solve(u, v, k, 1);
129             ll ans2 = solve(u, v, k-1, 0);
130             if (k == 0)
131                 ans1 += (v-u+1);                            // 考虑形如[a, a]的区间
132             printf("%I64d\n", ans1-ans2 );
133         }
134     }
135     return 0;
136 }

转载于:https://www.cnblogs.com/oneshot/p/4384639.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > C#如何操作另一个窗体：[2]子窗体操作主窗体(转)
下一篇 > csu 1536 Bit String Reordering(模拟 bfs+状态压缩)

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

HDU5196--DZY Loves Inversions 树状数组 逆序数

相关文章

HDU5196--DZY Loves Inversions 树状数组逆序数