hdu 3854 Glorious Array

Problem Description
You are given a array with N nodes. The array nodes are numbered from 1 to N ( represented by a_i ). In the start, the color
of any node in the array is white or black. We define that the "distance" between a and b is min{a_i| a<=i<=b} if a-th and bth
nodes have diffrerent color, or infinite if they have the same color.
We will ask you to perfrom some instructions of the following form:
0 i : change the color of the i-th node (from white to black, or from black to white);
or
1 : ask for the kinds of diffrent pair of nodes' distance is less than K
 
Input
The first line contains a positive integer: the number of test cases, at most 100.
After that per test case:
One line with three integers N, m and K (1 ≤ N, m ≤ 1 00000, K ≤ 1000000): the length of the array, the number of
instructions and K which used in operation 1 .
Then comes a line with N intergers a_i (|a_i|<10000000).
A line with N intergers c_i (c_i = 0(white) or 1(black)), which reprsent the color of N nodes.
Next m lines, each will be a instruction described above.
 
Output
one interger for each operation 1.
 
Sample Input
1 5 3 2 2 3 1 4 2 0 1 0 1 1 1 0 2 1
 
Sample Output
5 6
//
제목 설명: n 개의 숫자 와 각 숫자의 상태 (0 또는 1) 를 드 립 니 다.두 가지 조작 이 있 습 니 다. 첫 번 째 는 어떤 숫자 를 뒤 집 는 상태 입 니 다.두 번 째: 질문, 조건 을 만족 시 키 는 i, j 조합 개 수 를 입력 해 야 합 니 다.조건 을 만족 시 키 는 i, j 요구: A: 1 < = i < = j < = nB: i 와 j 숫자의 상태 가 다 릅 니 다.그 다음 에 매번 의 반전 상태 에 대해 조합 개 수 를 업데이트 합 니 다. 예 를 들 어 i 를 뒤 집 습 니 다. 만약 에 x [i] < k 가 있 으 면 i 왼쪽 에 0 또는 1 (구체 적 으로 x [i] 현재 상태) 이 몇 개 있 는 지, i 오른쪽 과 0 또는 1 (동상) 이 몇 개 있 는 지 보면 이번 반전 이 구체 적 으로 얼마나 변 했 는 지 알 수 있 습 니 다. 구체 적 인 실현 은 트 리 배열 을 사용 할 수 있 습 니 다.만약 x [i] > k 라면 초기 화 할 때 i 왼쪽 에 있 는 k 보다 작은 숫자의 위 치 를 기록 하 십시오. L [i], 같은 이치 로 R [i].L [i] 왼쪽 0 또는 1 의 개수 와 R [i] 오른쪽 0 또는 1 의 개 수 를 찾 으 면 이번 변화의 개수 입 니 다.이해 하기 쉬 울 거 야.코드 는 다음 과 같 습 니 다:
#include
#include
#include
using namespace std;
#define typev int // type of res
#define N 200000
typev ar[N]; // index: 1 ~ N
int lowb(int t) { return t & (-t) ; }
void add(int i, typev v)
{for ( ; i < N; ar[i] += v, i += lowb(i));}
typev sum(int i)
{
    typev s = 0;
    for ( ; i > 0; s += ar[i], i -= lowb(i));
    return s;
}
int n, m, k;
long long nowans;
int x[N], L[N], R[N], sta[N];
void init()
{
    memset(L, -1, sizeof(L)); memset(R, -1, sizeof(R));
    memset(ar, 0, sizeof(ar));
    for(int i = 1; i <= n; i++) if (x[i] < k)
        for(int j = i + 1; j <= n && x[j] >= k; j++)
            L[j] = i;
    for(int i = n; i >= 1; i--) if (x[i] < k)
        for(int j = i - 1; j >= 1 && x[j] >= k; j--)
            R[j] = i;
}
int Get(int l, int r, int now)
{
    //printf("l %d r %d %d %dn", l, r, sum(r), sum(l - 1));
    if (l > r) return 0;
    if (l == -1 || r == -1) return 0;
    if (now == 0) return r - l + 1 - (sum(r) - sum(l - 1));
    return sum(r) - sum(l - 1);
}
int main()
{
    int t;scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
        init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &sta[i]);
            if (sta[i]) add(i, 1);
        }
        nowans = 0;
        for(int i = 1; i <= n; i++)
            if (x[i] < k) nowans += Get(i + 1, n, !sta[i]);
            else nowans += Get(R[i], n, !sta[i]);
        //cout << nowans << endl;
        while(m--)
        {
            int tmp;scanf("%d", &tmp);
            if (tmp == 1) cout << nowans << endl;
            else
            {
                scanf("%d", &tmp);
                int before = 0, after = 0;
                int i = tmp;
                if (x[tmp] < k)
                {
                    before += Get(1, i - 1, !sta[i]) + Get(i + 1, n, !sta[i]);
                    after += Get(1, i - 1, sta[i]) + Get(i + 1, n, sta[i]);
                }else
                {
                    before += Get(1, L[i], !sta[i]) + Get(R[i], n, !sta[i]);
                    after += Get(1, L[i], sta[i]) + Get(R[i], n, sta[i]);
                }
                if (sta[i] == 0) add(i, 1), sta[i] = 1;
                else add(i, -1), sta[i] = 0;
                nowans += (after - before);
            }
        }
    }
    return 0;
}