[每日一题] NC19913 [CQOI2009]中位数图

题目大意：给定1,2,...,n的排列，和一个pivot number，求多少个长度为奇数的连续自序列的中位数恰好为这个pivot number。

https://ac.nowcoder.com/acm/problem/19913

因为没给数据范围，首先测了一下OJ，发现O(n^3) TLE，O(n^2) WA。所以先思考quadratic solution，并不困难，就是能否用amortized O(1)更新每个区间是否符合要求，那么判断是否中位数为pivot number只需要能维护大于该数、小于该数、等于该数的count。对于每个左端点L，遍历右端点即可，当然要忽略掉长度为偶数的情况。

此时直觉上认为可以降低为线性时间，于是考虑了一下需要的信息其实可以表示为有一个数组，每个元素为1（对应大于pivot number），-1（对应小于pivot number），0（对应等于pivot number）。要求的是多少个continuous subarray总和为0，且包含0。熟知这个问题的变体，就是给一个1和-1的数组如何求总和为continuous subarray的个数，用一个前缀的dictionary即可。每次看到R考虑多少个L满足，就是多少个之前的L - 1的前缀等于当前的前缀。那么只要稍加修改，对于奇数和偶数下标的前缀和分别计数就可以解决这个变体。以下代码省去boilerplate部分。

#include <bits/stdc++.h>

ll doit(int n, int b, VI& p) {
  u_m<int, int> even_index, odd_index;
  odd_index[0]++;
  int curr_sum = 0;
  ll ans = 0;
  REP(i,n){
    int curr = (p[i]>b)?1:((p[i]==b)?0:-1);
    curr_sum += curr;
    ans += (i%2)?even_index[curr_sum]:odd_index[curr_sum];
    if(i%2)odd_index[curr_sum]++;
    else even_index[curr_sum]++;
  }
  return ans;
}

int main(int argc, char* argv[]) {
  read2int(n,b);
  readvi(p,n);
  printlong(doit(n,b,p));
  return 0;
}