CF1424G

前缀和+离散化+端点维护

为什么现在总是想用树状数组？！！！

服了画蛇添足

离散化数组开两倍空间竟然写成 maxn >> 1 WA了两罚

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #define ll long long
 5 using namespace std;
 6 const int maxn = 2e5 + 10;
 7 int n, mx;
 8 int t[maxn];
 9 int l[maxn];
10 int r[maxn];
11 int p[maxn >> 1];
12 
13 int lowbit(int x)
14 {
15     return x & -x;
16 }
17 
18 void add(int x, int val)
19 {
20     for(int i = x ; i <= mx ; i += lowbit(i)){
21         t[i] += val;
22     }
23 }
24 
25 int getsum(int x)
26 {
27     int ans = 0;
28     for(int i = x ; i >= 1 ; i -= lowbit(i)){
29         ans += t[i];
30     }
31     return ans;
32 }
33 
34 int main(){
35     scanf("%d",&n);
36     int tot = 0;
37     for(int i = 1 ; i <= n ; i++){
38         scanf("%d%d",&l[i],&r[i]);
39         p[++tot] = l[i];
40         p[++tot] = r[i];
41     }
42     sort(p + 1, p + tot + 1);    
43     tot = unique(p + 1, p + tot + 1) - p - 1;
44     for(int i = 1 ; i <= n ; i++){
45         l[i] = lower_bound(p + 1, p + tot + 1, l[i]) - p;
46         r[i] = lower_bound(p + 1, p + tot + 1, r[i]) - p;
47         mx = max(mx, r[i]);
48     }
49     
50     for(int i = 1 ; i <= n ; i++){
51         add(l[i], 1);
52         add(r[i], -1);
53     }
54     
55     int tar, res = 0;
56     for(int i = 1 ; i <= tot ; i++){
57         int k = getsum(i);
58         if(k > res){
59             res = k;
60             tar = p[i];
61         }
62     }
63     printf("%d %d
",tar,res);
64     return 0;
65 }

只要前缀和就行了。树状数组还是重在每次加入数据的维护。如果只是在所有数据处理完的末端进行查询，或许就没有必要应用树状数组了。

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
int n, mx;
int l[maxn], r[maxn];
int p[maxn << 1];
int res[maxn];
int pre[maxn];

int main(){
    scanf("%d",&n);
    int tot = 0;
    for(int i = 1 ; i <= n ; i++){
        scanf("%d%d",&l[i],&r[i]);
        p[++tot] = l[i];
        p[++tot] = r[i];
    }
    sort(p + 1, p + tot + 1);    
    tot = unique(p + 1, p + tot + 1) - p - 1;
    for(int i = 1 ; i <= n ; i++){
        int le = lower_bound(p + 1, p + tot + 1, l[i]) - p;
        int ri = lower_bound(p + 1, p + tot + 1, r[i]) - p;
        pre[le] = l[i];
        pre[ri] = r[i];//pre[]存储离散化前的端点 
        res[le]++;
        res[ri]--;
        mx = max(mx, r[i]);
    }
    
    int ans = 0, pos;
    for(int i = 1 ; i <= tot ; i++){
        res[i] += res[i - 1];
        if(res[i] > ans){
            ans = res[i];
            pos = pre[i];
        }
    }
    printf("%d %d
",pos,ans);
    
    return 0;
}