AcWing 43场周赛第3题 4316. 合适数对

这是AcWing 43场周赛的最后一道题

详细题意看4316. 合适数对 - AcWing题库

题意的大概意思是：给一个整数数列 和一个比较大的数m，求在这个序列1~n中存在多少个数对(l,r)满足该区间和小于m。

就是求动态区间和小于m的个数。

数据的范围：1≤n≤2×105">1≤n≤2*10^5 , |t|≤2×1014">|t|≤2×10^14，|ai|≤109">|ai|≤10^9

1≤n≤2×105">|t|≤2×1014">|ai|≤109">首先，这个题考的基础是：前缀和数组

1≤n≤2×105">|t|≤2×1014">|ai|≤109">暴力n^2，肯定过不了，只能想想别的办法

1≤n≤2×105">|t|≤2×1014">|ai|≤109">先把公式写出来  s ( r ) -  s ( l - 1 ) > m

1≤n≤2×105">|t|≤2×1014">|ai|≤109">我们不妨枚举右端点 r , 那么 变成  s ( l - 1) < s ( r ) - m

1≤n≤2×105">|t|≤2×1014">|ai|≤109">想到树状数组，树状数组就是更改动态区间，求动态排名

1≤n≤2×105">|t|≤2×1014">|ai|≤109">由于数据值域比较大，树状数组一定开不下，所以要离散化

1≤n≤2×105">|t|≤2×1014">|ai|≤109">这里就是要求 动态排名

1≤n≤2×105">|t|≤2×1014">|ai|≤109">我们不妨将s [ l -1 ] 和 s [ r ] -m 都存在离散数组里  数组大小就是4*10^5

1≤n≤2×105">|t|≤2×1014">|ai|≤109">再用树状数组 每次加入一个点 就 看看左边有多少个s [ l - 1 ]满足条件 ( 这里就是看动态排第几名）

1≤n≤2×105">|t|≤2×1014">|ai|≤109">再将该位置加上1 ，方便后面计算。

1≤n≤2×105">|t|≤2×1014">|ai|≤109">下面看代码：

 1 #include 
 2 
 3 using namespace std;
 4 typedef long long LL;
 5 const int N=4e5+10;
 6 
 7 int n;
 8 int a[N];
 9 int tre[N];//sx是离散化数组
10 LL res,m,sx[N];
11 int cnt;
12 LL s[N];
13 
14 //离散化可以理解为 数组的大小顺序排列用下标表示
15 int get(LL x)//二分法求离散后的数
16 {
17     int l=1,r=cnt;
18     while(l<r)
19     {
20         int mid=l+r>>1;
21         if(sx[mid]>=x)r=mid;
22         else l=mid+1;
23     }
24     return l;
25 }
26 
27 int lowbit(int x)
28 {
29     return x&-x;
30 }
31 
32 void add(int x,int c)
33 {
34     for(int i=x;ic;
35 }
36 
37 int sum(int x)
38 {
39     int res=0;
40     for(int i=x;i;i-=lowbit(i))res+=tre[i];
41     return res;
42 }
43 
44 
45 int main()
46 {
47     scanf("%d%lld",&n,&m);
48     
49     for(int i=1;i<=n;i++)
50     {
51         scanf("%d",&a[i]);
52     }
53     
54     sx[++cnt]=0,sx[++cnt]=0-m;//树状数组的下标为1，所以要++cnt
55     //由于前缀和一般是s[r]-s[l-1],l是从1开始,l-1可能为0
56     //这也是需要的离散化的，所以先离散化。
57     
58     //s[r]-s[l-1]>m  
59     //枚举右断点r 那么s[l-1]需要满足s[l-1]>s[r]-m
60     //所以将s[l-1]和s[r]-m全部都离散化再用树状数组求即可
61     for(int i=1;i<=n;i++)
62     {
63         s[i]=s[i-1]+a[i];
64         sx[++cnt]=s[i];
65         sx[++cnt]=s[i]-m;
66     }
67     
68     sort(sx+1,sx+1+cnt);
69     cnt=unique(sx+1,sx+1+cnt)-sx-1;//离散化去重
70     
71     //先把0的离散化加进去
72     add(get(0),1);
73     
74     LL res=0;
75     for(int i=1;i<=n;i++)
76     {
77         res+=i-sum(get(s[i]-m));
78         add(get(s[i]),1);
79     }
80     
81     cout<endl;
82     
83     return 0;
84 }

总结一下： 树状数组很方便，但是往往维护的范围很小，如果数的值域比较大，一般用离散化来帮忙。

ps:   离散化一定要去重

ps+：树状数组一般从1开始，所以离散化时候一定要从1开始。

ps++： 树状数组加的时候，一定要加到整个数组大小