洛谷 3660 bzoj 4994 Why Did the Cow Cross the Road III 题解

发表于 | 阅读次数：
本文字数： 679 字 | 阅读时长 ≈ 3 分钟

题意简述

（bzoj，十分简洁，直接蒯来了）
给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数
n<=1e5。

思路

相当于有$n$个区间$a_i,b_i$，求相交的区间对数。

那么我们把它转化为，对于每个$a_i,b_i$，统计区间里面包含多少其它区间的左端点或右端点，而它的另一个端点不能出现在$[a_i,b_i]$中。

那么能否直接求包含的端点数呢？可以！我们把区间按长度从大到小排序，那么已经考虑的区间肯定比当前的区间长，不珂能出现两个端点同时在里面的情况。然后直接用树状数组统计端点数即珂。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define int long long  //记得开long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class BIT
    {
        public:
            int tree[N];
            int len;
            void BuildTree(int _len)
            {
                len=_len;
                FK(tree);
            }
            void Add(int pos,int val=1)
            {
                for(int i=pos;i<=len;i+=(i&(-i)))
                {
                    tree[i]+=val;
                }
            }
            int Query(int pos)
            {
                int ans=0;
                for(int i=pos;i>0;i-=(i&(-i)))
                {
                    ans+=tree[i];
                }
                return ans;
            }
            int RQuery(int l,int r){return Query(r)-Query(l-1);}
    }T;
    struct node{int l,r;}a[N]; bool operator<(node a,node b){return a.r-a.l>b.r-b.l;} //从大到小排序
    int n;
    void Input()
    {
        MEM(a,-1);
        R1(n);
        F(i,1,2*n)
        {
            int x;R1(x);
            if (a[x].l==-1) a[x].l=i;
            else a[x].r=i;
        }
        //读入的时候顺便求出n个区间的左端点，右端点
    }

    void Soviet()
    {
        sort(a+1,a+n+1);
        int ans=0;
        T.BuildTree(100000);
        F(i,1,n)
        {
            ans+=T.RQuery(a[i].l,a[i].r);
            T.Add(a[i].l,1); T.Add(a[i].r,1);
        }
        printf("%lld\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w