//高考后第一次回vijos，看来手感还没下降太多QwQ
//此题与选择客栈有一点相似之处
//找到我们要的数的位置，然后从这个位置往左往右分别扫一遍
//往右扫的过程中，y[i]表示b右边比b大的数有i个的区间的数量（很绕是不是）
//z[i]就表示b左边比b小的数有i个区间的数量
//这里为了防止数组下标出现负数，把初值设为n
//这样的话所有y[]*z[]加起来就是答案
//注意z[0]与与y[0]还要单独加上
//另外b本身作为一个区间也是可以的，所以答案要再+1
#include<iostream>
using namespace std;
int a[100010],z[200010],y[200010];
int main()
{
    int n,b,i,w,now,sum=0;
    cin>>n>>b;
    for(i=1;i<=n;i++)
     {
        cin>>a[i];
        if(a[i]==b)
         w=i;
     }
    now=n;
    for(i=w+1;i<=n;i++)
     {
        if(a[i]>a[w])
         now++;
        else
         now--;
        y[now]++;
     }
    now=n;
    for(i=w-1;i>0;i--)
    {
        if(a[i]>a[w])
         now--;
        else
         now++;
        z[now]++;
    }
    for(i=0;i<=2*n+1;i++)
     sum+=z[i]*y[i];
    sum+=z[n]+y[n];
    cout<<sum+1;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int n, b, pos, a[maxn], f[maxn * 2];
ll res;

int main() {
    scanf("%d %d", &n, &b);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] == b) {
            pos = i;
        }
    }
    ll cur = 0;
    for (int i = pos; i >= 1; i--) {
        cur += (a[i] < b);
        cur -= (a[i] > b);
        f[cur + 100000]++;
    }
    cur = 0;
    for (int i = pos; i <= n; i++) {
        cur += (a[i] > b);
        cur -= (a[i] < b);
        res += f[cur + 100000];      
    }
    printf("%lld\n", res);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int num[maxn];
int sum[maxn];
int cnt[maxn << 1];

int main()
{
    int n, b, k, index = -1;
    cin >> n >> b;
    for (int i = 1; i <= n; i++)
    {
        cin >> k;
        if(k < b)
            num[i] = -1;
        else if(k == b)
            index = i;
        else
            num[i] = 1;
        sum[i] = sum[i - 1] + num[i];
        if(index == -1)
            cnt[sum[i] + n]++;
    }

    cnt[n]++;       //前缀和为0时, 就是表示区间1~i, 不能直接用前缀差表示, 就是i的前缀和
    
    int ans = 0;
    for (int i = index; i <= n; i++)
        ans += cnt[sum[i] + n];
    cout << ans << endl;

    return 0;
}

#include<iostream>
using namespace std;
int n,b;
int da[100010];
int lct[2][100010],rct[2][100010];
int main () {
    
    ios::sync_with_stdio(false);
    cin>>n>>b;
    int pos=0;
    for(int i=1;i<=n;i++) {
        cin>>da[i];
        if (da[i]<b) da[i]=-1;
        else if (da[i]>b) da[i]=1;
        else pos=i,da[i]=0;     
    }
    int sum=0;
    for(int i=pos;i>=1;i--) {
        sum+=da[i];
        if (sum>0) lct[1][sum]++;
        else lct[0][-sum]++;
    }
    sum=0;
    for(int i=pos;i<=n;i++) {
        sum+=da[i];
        if (sum<0) rct[1][-sum]++;
        else rct[0][sum]++;     
    }
    int ans=0;
    for(int i=0;i<=100010;i++) 
      for(int j=0;j<=1;j++) 
        ans+=lct[j][i]*rct[j][i];
    cout<<ans<<endl;
    return 0;
    
}

哦，对了，记住是排序，b只会出现一次。

过气Pascal最后的续命....
刚开始没处理好边界，狂刷10次全WA...

比之前交的代码更短了，就18行，时间内存都优化了，但可读性变差了，代码已经瘦的不成样了......
不要什么数据结构，统计一下就行了。楼下的楼下有个相似方法，但C++的代码比我长，因为--C++没有负的数组下标，要特殊处理.....
每读一个数处理一次，读完答案也出来了，已经没法再快了。
var
a,n,b,i,m,ans,sum:longint;
left:array[-100000..100000] of longint;
begin
readln(n,b);
fillchar(left,sizeof(left),0);
sum:=0; left[0]:=1;
for i:=1 to n do
begin
read(a);
if a>b then inc(sum) else if a<b then dec(sum) else if a=b then begin m:=i+1; break end;
inc(left[sum]);
end;
ans:=left[sum];
for i:=m to n do
begin read(a); if a>b then inc(sum) else if a<b then dec(sum); ans:=ans+left[sum]; end;
writeln(ans);
end.

总计50ms，1MB，复杂度O(n)，应该都是最小的了吧。评测机变牛逼了，<15ms已经不能糊弄程0ms了，0msAC已成上古神话......

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 100000 + 5;

int n, b, num[N], a[N], sum[N][2];

int main() {
scanf("%d%d", &n, &b);
int pos = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] == b) { num[i] = num[i - 1]; pos = i; }
else if (a[i] < b) num[i] = num[i - 1] - 1;
else if (a[i] > b) num[i] = num[i - 1] + 1;
}
int ans = 0;
for (int i = pos; i >= 1; i--) {
int x = num[pos] - num[i - 1];
if (x < 0) sum[-x][0]++;
else if (x > 0) sum[x][1]++;
else sum[0][0]++;
}
for (int i = pos; i <= n; i++) {
int x = num[i] - num[pos];
if (x > 0) ans += sum[x][0];
else if (x < 0) ans += sum[-x][1];
else ans += sum[0][0];
}
printf("%d\n", ans);
return 0;
}

偷懒用了个map，不然可以再快些

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define rep(id,a,b) for(int id=(a);id<(b);++id)
#define irep(id,a,b) for(int id=(a);id>(b);--id)
#define reset(arr,c) memset(arr,c,sizeof(arr))

typedef long long int64;

#include <map>

const int maxN = 100000 + 5;

int N, B;
int s[maxN];

void input()
{
scanf ("%d%d", &N, &B);
rep (i, 0, N) scanf ("%d", s + i);
}

int64 solve()
{
int64 ans (1);
map<int, int> cnt;
int pos = 1;
while (s[pos] != B) ++pos;
int tp = 0;
irep (i, pos - 1, -1)
{
if (s[i] < B) ++tp;
else --tp;
if (tp == 0) ++ans;
if (!cnt.count (tp) ) cnt[tp] = 1;
else ++cnt[tp];
}
tp = 0;
rep (i, pos + 1, N)
{
if (s[i] > B) ++tp;
else --tp;
if (tp == 0) ++ans;
ans += cnt[tp];
}
return ans;
}

int main()
{
input();
printf ("%lld\n", solve() );
return 0;
}

大神帮我看看错哪了，显示Runtime Error
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001], s[100001], f[100001];
int main()
{
int n, b, k = 1, ans = 0;
scanf("%d%d", &n, &b);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] == b) k = i, a[i] = 0;
else if (a[i] > b)a[i] = 1;
else a[i] = -1;
}
for (int i = k - 1; i > 0; i--)
s[i] = s[i + 1] + a[i];
for (int i = k + 1; i <= n; i++)
s[i] = s[i - 1] + a[i];
for (int i = k; i > 0; i--)
f[s[i]]++;
for (int i = k; i <= n; i++)
ans += f[-s[i]];
cout << ans << endl;
return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef bool boolean;
#define smin(a, b)  (a) = min((a), (b))
#define smax(a, b)  (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
    char x;
    while(!isdigit((x = getchar())));
    for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
    ungetc(x, stdin);
}

int n, m;
int pos;
int* list;

inline void init(){
    readInteger(n);
    readInteger(m);
    list = new int[(const int)(n + 1)];
    for(int i = 1; i <= n; i++){
        readInteger(list[i]);
        if(list[i] == m)    pos = i;
    }
}

inline int calc(int less, int more){
    return (less < more) ? (n - less + more) : (less - more);
}

int result;
int* buffer;
inline void solve(){
    buffer = new int[(const int)(n * 2 + 1)];
    int more = 0, less = 0;
    memset(buffer, 0, sizeof(int) * (n * 2 + 1));
    buffer[0] = 1;
    for(int i = pos + 1; i <= n; i++){
        if(list[i] > list[pos]) more++;
        else less++;
        buffer[calc(less, more)]++;
    }
    more = less = 0;
    for(int i = pos; i >= 1; i--){
        if(list[i] > list[pos]) more++;
        else if(i != pos)   less++;
        result += buffer[calc(more, less)];
    }
    printf("%d", result);
}

int main(){
    init();
    solve();
    return 0;
}

看我的博客吧，有详解
http://blog.sina.com.cn/s/blog_13639e4180102wdj6.html

记录信息
评测状态 Accepted
题目 P1549 中位数
递交时间 2015-10-05 20:52:24
代码语言 C++
评测机 VijosEx
消耗时间 76 ms
消耗内存 2620 KiB
评测时间 2015-10-05 20:52:26
评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:46:24: warning: unknown conversion type character 'l' in format [-Wformat=]
printf("%lld\n",ans);
^
foo.cpp:46:24: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 0 ms, mem = 2616 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2620 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 2620 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2620 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 2620 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 2620 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 2620 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 2620 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 2616 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 2620 KiB, score = 10

Accepted, time = 76 ms, mem = 2620 KiB, score = 100
代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <memory>
#include <iostream>
using namespace std;

int num[100001],sum[100001],l[200001],r[200001],n,b,point;
long long ans;

int main()
{
scanf("%d %d\n",&n,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
if(num[i]>b)
{
num[i]=1;
}
else if(num[i]==b)
{
num[i]=0;
point=i;
}
else num[i]=-1;
}
l[n]=1;
r[n]=1;
for(int i=point-1;i>=1;i--)
{
sum[i]=sum[i+1]+num[i];
l[sum[i]+n]++;
}
for(int i=point+1;i<=n;i++)
{
sum[i]=sum[i-1]+num[i];
r[sum[i]+n]++;
}
for(int i=0;i<=2*n-1;i++)
{
ans+=l[i]*r[2*n-i];
}
printf("%lld\n",ans);
return 0;
}

AC60题啦！纪念一下。。。不要吐槽。。。。

#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=100000 + 10;

long int num[MAXN], f[MAXN], sum[MAXN][2];

int main()
{
int n, a, b, bri, ans=0;
scanf("%d%d",&n,&b);

for(int i=1; i<=n; i++){
scanf("%d",&num[i]);
if(num[i] < b)
f[i] = f[i-1] - 1;
else if(num[i] > b)
f[i] = f[i-1] + 1;
else if(num[i] == b){
bri = i;
f[i] = f[i-1];
}
}
for(int i=bri-1; i>=0; i--){
a = f[bri] - f[i];
if(a < 0)
sum[-a][0]++;
else if(a > 0)
sum[a][1]++;
else
sum[0][0]++;
}
for(int j=bri; j<=n; j++){
a = f[j] - f[bri-1];
if(a > 0)
ans += sum[a][0];
else if(a < 0)
ans += sum[-a][1];
else
ans += sum[0][0];
}
printf("%d",ans);
return 0;
}
水一发~~

P1549中位数
Accepted

记录信息

评测状态 Accepted
题目 P1549 中位数
递交时间 2015-02-10 23:40:23
代码语言 C++
评测机 VijosEx
消耗时间 361 ms
消耗内存 1944 KiB
评测时间 2015-02-10 23:40:24

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1652 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1652 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 1656 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 1648 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1652 KiB, score = 10

测试数据 #5: Accepted, time = 27 ms, mem = 1680 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 1652 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 1692 KiB, score = 10

测试数据 #8: Accepted, time = 39 ms, mem = 1660 KiB, score = 10

测试数据 #9: Accepted, time = 249 ms, mem = 1944 KiB, score = 10

Accepted, time = 361 ms, mem = 1944 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <map>

using namespace std;

int n , b;
int i;
int a[100000 + 10];
int is[100000 + 10];
int pre[100000 + 10];
int pos;
map < int , int > m;
int ans;

int main()
{
scanf( "%d %d" , &n , &b );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
for( i = 0 ; i < n ; i++ )
if( a[i] > b )
is[i] = -1;
else if( a[i] < b )
is[i] = 1;
else
{
pos = i;
is[i] = 0;
}
pre[0] = is[0];
for( i = 1 ; i < n ; i++ )
pre[i] = pre[ i - 1 ] + is[i];
for( i = pos ; i < n ; i++ )
if( m.find( pre[i] ) != m.end() )
m[ pre[i] ]++;
else
m[ pre[i] ] = 1;
for( i = 0 ; i < pos ; i++ )
ans += m[ pre[i] ];
ans += m[ 0 ];
cout << ans << endl;
return 0;
}

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include<string.h>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define exp 1e-8
#define maxn 100010
#define set(a,b) memset(a,b,sizeof(a));
void bug(string st="bug")
{cout<<st<<endl;}
int num[maxn];
int lmin[maxn]={0};
int lmax[maxn]={0};
int rmin[maxn]={0};
int rmax[maxn]={0};
int main()
{
int n,d;
scanf("%d %d",&n,&d);
int idx=0;
for(int i=1;i<=n;i++)
{
int temp;
scanf("%d",&temp);
if(temp==d)
idx=i;
else if(temp>d)
num[i]=1;
else num[i]=-1;
}
int sum=0;
for(int i=idx+1;i<=n;i++)//r
{
sum+=num[i];
if(sum>=0)
rmax[sum]++;
else
rmin[-sum]++;
}
sum=0;
for(int i=idx-1;i>=1;i--)//r
{
sum+=num[i];
if(sum>=0)
lmax[sum]++;
else
lmin[-sum]++;
}
int ans=lmax[0]+rmax[0]+1+lmax[0]*rmax[0];
for(int i=1;i<=n;i++)
{
if(lmax[i]!=0)
ans+=lmax[i]*rmin[i];
if(lmin[i]!=0)
ans+=lmin[i]*rmax[i];
}
cout<<ans<<endl;
return 0;
}

{
将小于b的数改为-1，等于b的改为0，大于b的改为1，统计前缀和
并建立主席树，设b的位置为pos
枚举左端点0..pos-1
对答案贡献为[pos,n]里sum[i]出现的次数
O(nlogn)
}
const
maxn = 5000000;
type
node = record
a,b : longint;//[a,b]
l,r : longint;//left,right
data : longint;//Data : 里面数字的个数
end;
var
seg : array[0..maxn] of node;
tot : longint;
a,tmp,head : array[0..100010] of longint;
n,i,x,b,pos : longint;
ans : int64;
procedure build(a,b : longint);
var
mid,id : longint;
begin
inc(tot);
id := tot;
seg[id].a := a;
seg[id].b := b;
if a = b then exit;
mid := (a + b) >> 1;
seg[id].l := tot+1;
build(a,mid);
seg[id].r := tot+1;
build(mid+1,b);
end;
procedure insert(x,nownode : longint);
var
mid : longint;
begin
inc(tot);
seg[tot].a := seg[nownode].a;
seg[tot].b := seg[nownode].b;
seg[tot].data := seg[nownode].data+1;
mid := (seg[tot].a + seg[tot].b) >> 1;
if x <= mid then
begin
seg[tot].r := seg[nownode].r;
if seg[nownode].l > 0 then begin
seg[tot].l := tot+1;
insert(x,seg[nownode].l);
end;
end
else
begin
seg[tot].l := seg[nownode].l;
if seg[nownode].r > 0 then begin
seg[tot].r := tot+1;
insert(x,seg[nownode].r);
end;
end;
end;
function query(k,l,r : longint) : int64;
var
mid : longint;
begin
repeat
if seg[r].a = seg[r].b then exit(seg[r].data-seg[l].data);
mid := (seg[r].a + seg[r].b) >> 1;
if k <= mid then
begin
r := seg[r].l;
l := seg[l].l;
end
else
begin
r := seg[r].r;
l := seg[l].r;
end;
until false;
end;
begin
read(n,b);
for i := 1 to n do
begin
read(x);
if x = b then
begin
pos := i;continue;
end;
if x < b then
tmp[i] := -1
else
tmp[i] := 1;
end;
a[0] := n+1;
for i := 1 to n do a[i] := a[i-1]+tmp[i];
build(1,n*2+10);
head[0] := 1;
for i := 1 to n do
begin
head[i] := tot+1;
insert(a[i],head[i-1]);
end;
for i := 0 to pos-1 do
ans := ans + query(a[i],head[pos-1],head[n]);
writeln(ans);
end.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 300000
#define D 100001

int f[MAXN];
int a[MAXN];
int b,n,t;
int s1[MAXN],s2[MAXN];

int main(){
scanf("%d%d",&n,&b);
s1[0]=0;
s2[0]=0;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
if (a[i]<b){
s1[i]=s1[i-1]+1;
} else s1[i]=s1[i-1];
if (a[i]>b){
s2[i]=s2[i-1]+1;
} else s2[i]=s2[i-1];
if (a[i]==b){
t=i;
}
}
memset(f,0,sizeof(f));
f[0+D]=1;
for (int i=t;i++<n;){
f[(s2[i]-s2[t])-(s1[i]-s1[t])+D]++;
}
/* for (int i=-10;i<=10;i++){
printf("%d:%d\n",i,f[i+D]);
}*/
int ans=0;
for (int i=0;i++<t;){
// printf("%d:%d\n",i,f[-((s2[t-1]-s2[i-1])-(s1[t-1]-s1[i-1]))+D]);
ans+=f[-((s2[t-1]-s2[i-1])-(s1[t-1]-s1[i-1]))+D];
}
printf("%d\n",ans);
return 0;
}

h:array[-100000..100000]of longint;

用hash表求f[i]+f[j]=0的个数，根据排列组合的原则，hash表一定不能开成boolean!我在这了wa几次。

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

20行的程序。。。

很爽。。

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

补充“三代水影·游”的最后一步。。

用一个数组来记录值为s[i]时有多少个，

无外乎这几句，

for i:=k downto 1 do inc(f[s[i]]);

for i:=k to n do inc(ans,f[s[i]]);

因为s是统计大了多少个和小了多少个的差，

中间有一个S值为零的K，两边一共是偶数个，加上中间的一个，

这样就一定是奇数个了。。。

得证，最后结果不需要奇偶判断。。。。。

不过我的F数组要开很大。。

空间需求大（空间换时间）。。。

超水

O（rec)就可以出解 rec表示中位数所在的位置编号

hash表记录一下就行了