BZOJ1303 [CQOI2009]中位数图【乱搞】-白红宇

BZOJ1303 [CQOI2009]中位数图【乱搞】

阅读量：4879 次

发布时间：2019-06-11

本文共 1528 字，大约阅读时间需要 5 分钟。

1303: [CQOI2009]中位数图

Time Limit: 1 Sec

Memory Limit: 162 MB

Submit: 3086

Solved: 1898

[ ][ ][ ]

Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

Input

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

HINT

第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}

N<=100000

很水的一道题，为何我会想到主席树= =

由于是一个排列，所以b只有一个

我们找到b，要做的就是由b的位置开始扩展，使得扩展出来的数中大于b的个数和小于b的个数相等

我们开一个数组sum[x]表示b向左扩展出大于b个数 - 小于b个数 = x的方案数z

对应我们只要找到一个b向右扩展小于b的个数 - 大于b的个数 = x的位置，ans就可以加上z

#include
    
     #include
     
      #include
      
       #include
       
        #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define fo(i,x,y) for (int i = (x); i <= (y); i++)#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)using namespace std;const int maxn = 100005,maxm = 200005,INF = 1000000000;inline int read(){	int out = 0,flag = 1;char c = getchar();	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}	return out * flag;}int A[maxn],n,pos,b,sum[maxm];LL ans = 0;int main(){	n = read(); b = read();	REP(i,n) if ((A[i] = read()) == b) pos = i;	sum[pos] = 1;	for (int i = 1,tot = 0; i < pos; i++){		if (A[pos - i] < b) tot--;		else tot++;		sum[tot + pos]++;	}	ans = sum[pos];//cout<
        
         <
         
           b) tot--; else tot++; ans += sum[tot + pos]; } cout<
          
           <