是啊...

O(n)的就可以了.

楼下繁了

１ＫＢ的程序

＞Ｋ就转成１

＜Ｋ就转成－１

计和

枚举起点扫描一遍就行了

Ｏ（Ｎ）

AC过的题，现在在外地，没程序，等回来再传吧……

提示一下：先列出一个满足要求的子序列所需满足的不等式，再用线段树统计个数

p.s. 原来我做的那题没说是一个排列……不过楼下的方法还是很巧妙（奇偶要分开讨论吧？）

假的hash表hhh其实就是桶？？？表示不会hash，反正勉强做到o(n)，但为啥还是好慢2333

#include<iostream>
#include<set>
using namespace std;
set<int>hashName;
int data[100000];
int hashTableR[200000];
int hashTableL[200000];
int main(void){
    int n,b,temp,pos;
    cin>>n>>b;
    for(int i=0;i<n;i++){
        cin>>temp;
        if(temp<b){
            data[i]=-1;
        }
        else if(temp>b){
            data[i]=1;
        }
        else{
            data[i]=0;
            pos=i;
        }
    }
    int Count=0;
    for(int i=1;i<=pos;i++){
        Count+=data[pos-i];
        hashTableL[Count+100000]++;
        hashName.insert(Count+100000);
    }
    Count=0;
    for(int i=1;i<n-pos;i++){
        Count+=data[pos+i];
        hashTableR[Count+100000]++;
    }
    int sum=0;
    for(const auto i:hashName){
        sum+=hashTableL[i]*hashTableR[200000-i];
    }
    sum+=hashTableL[100000]+hashTableR[100000];
    cout<<sum+1<<endl;
} 

顾名思义,就是要b的数的个数 

b序列中的位置为p

如果a[i]>b 就定义 a[i]=1

如果a[i]

啥叫水啊

虽然想到了怎么做，但是还是觉得是道好题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

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

var i,n,b,xx,yy,j,x,w:longint;

a:array[0..100003]of longint;

f1,f2:array[-100002..100002]of longint;

begin

readln(n,b);

for i:=1 to n do read(a[i]);

for i:=1 to n do

if a[i]=b then

begin

x:=0;

xx:=0;

yy:=0;

for j:=i-1 downto 1 do

begin

if a[j]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

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

一遍AC，庆祝一下。

这道题如果有思路了，就是个水题了，思路呢，不是很难。

读入时预处理一下，比b大的记为1，比b小的记为-1，这样能简化统计。p是b位置，即a[p]:=b;

数组s记录的是从p向两边倒i处的和

for i:=p-1 downto 1 do

s[i]:=s+a[i];

for i:=p+1 to n do

s[i]:=s+a[i];

这样就剩下最后一步了，求出s数组中p左右两边和为0的个数，这个就不说了，大家都有自己的做法，但一定要是O(n)的复杂度。这样全题的复杂度是O(n)仔细点就是

O(3n)