题解 P3608 【[USACO17JAN]Balanced Photo平衡的照片】

发表于 | 更新于 | 阅读次数：

诚然，$O(n^2)$的做法可以水过去，不过蒟蒻水了一发树状数组。
树状数组复杂度为$O(NlogN)$,非常完美。

我们先离散化数组，改用第几大来代替每次按原输入的数组，那么我们只要用树状数组来维护有几个比这个数大就行了，不过对于从左到右和从右到左，我们需要做两遍。代码（除了我的快读快输）也很短。

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
#define swap mswap
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
void swap(int &x,int &y)
{
    x^=y^=x^=y;
}
void read(int &x)
{
    x=0;
    char ch=getchar();
    int pd=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            pd=-pd;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=pd;
}
void write(const int &x)
{
    char f[100001];
    int s=0;
    int tmp=x;
    if(tmp==0)
    {
        putchar('0');
        return;
    }
    if(tmp<0)
    {
        tmp=-tmp;
        putchar('-');
    }
    while(tmp>0)
    {
        f[s++]=tmp%10+'0';
        tmp/=10;
    }
    while(s>0)
    {
        putchar(f[--s]);
    }
}

const int N=1e5+10;
int n,c[N],a[N],b[N];
int l[N],r[N];
int lowbit(int &x)
{
	return x&(-x);
	
}


void add1(int x)
{
	while(x<=n)
	{
		c[x]++;
		x+=lowbit(x);
	}
}
void add2(int x)
{
	while(x>0)
	{
		c[x]++;
		x-=lowbit(x);
	}
}


int query1(int x)
{
	int ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

int query2(int x)
{
	int ans=0;
	while(x<=n)
	{
		ans+=c[x];
		x+=lowbit(x);
	}
	return ans;
}
inline bool cmp(const int &x,const int &y)
{
	return x>y;
 } 
int main()
{
    read(n);
    for(register int i=1;i<=n;++i)
    {
        read(a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for(register int i=1;i<=n;++i)
    {
        int j=lower_bound(b+1,b+cnt+1,a[i])-b;
		add2(j);
        l[i]=query2(j+1);
    }
    memset(c,0,sizeof(c));
	for(register int i=n;i>=1;--i)
	{
		int j=lower_bound(b+1,b+cnt+1,a[i])-b;
		add2(j);
		r[i]=query2(j+1);
	}
	int aa=0;
	for(register int i=1;i<=n;++i)
	{
		if(max(l[i],r[i])>2*(min(l[i],r[i])))
		{
			aa++;
		}
	}
	write(aa);
}