[ZJ] a048. 函数增减性

http://zerojudge.tw/ShowProblem?problemid=a048

內容 ：

单调函数的增减性的判断想必大家都很清楚了吧...
这里有N个函数f₁(x),f₂(x),…,f_N(x)，开始时我告诉你他们全都是增函数。由于我记性不好，我会时不时发现哪个函数的增减性我说错了，要进行更改。当然，更改的话，肯定告诉你不是增（减）函数而是减（增）函数。

这里，我们定义一个函数F(x)=f_L(f_L+1(…f_R(x)…))，这里1<=L<=R<=N。

我想问问你F(x)是增函数还是减函数。

輸入說明 ：

输入的第一行是两个数N(1<=N<=200000)和Q(1<=Q<=200000)。
接下来有Q行，每行第一个数是v(v=1,2)。
若v=1，那么接着有一个数字i，表示这个是我记错了函数fi的增减性，那么你应该在这个操作之后认为fi函数的增减性与原来的相反；
若v=2，那么接着有两个数字L和R，表示询问你F(x)=f_L(f_L+1(…f_R(x)…))的增减性。

輸出說明 ：

对所有v=2的操作，输出F(x)的增减性。
若F(x)是增函数则输出0，若F(x)是减函数则输出1。

範例輸入 ：

5 32 2 41 32 2 4

範例輸出 ：

01

提示 ：

测资可能有误，欢迎推翻！

出處 ：

liouzhou_101 (管理：liouzhou_101)


題目有點難懂就是了，還好請了別人來幫我看看 ...

作法 : Binary indexed tree
你可以用微分發現(連鎖定理)
F(x)=f_L(f_L+1(…f_R(x)…))
F'(x)= f_L ' (f_L+1(…f_R(x)…)) * (f_L+1'(…f_R(x)…)) ...
只要查看減函數在[L,R]中的個數，就可以判定了

/**********************************************************************************/
/*  Problem: a048 "函数增减性" from liouzhou_101                             */
/*  Language: C                                                                   */
/*  Result: AC (112ms, 2588KB) on ZeroJudge                                       */
/*  Author: morris1028 at 2011-05-17 20:47:36                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
int Input() {
    char cha;
    unsigned int x = 0;
    while(cha = getchar())
        if(cha != ' ' && cha != '\n' || cha == EOF) break;
    if(cha == EOF) return -1;
    x = cha-48;
    while(cha = getchar()) {
        if(cha == ' ' || cha == '\n') break;
        x = x*10 + cha-48;
    }
    return x;
}  
int C[200001]={}, A[200001]={};
int lb[200001];
int Modify(int N, int flag) {
    while(N <= 200000) {
        C[N] += flag;
        N += lb[N];
    }
}
int Operator(int N) {
    int Sum = 0;
    while(N) {
        Sum += C[N];
        N -= lb[N];
    }
    return Sum;
}
main() {
    int N, Q, v, L, R, i;
    int a, b;

    for(a = 1; a <= 200000; a++)
        lb[a] = a & -a;
    scanf("%d %d", &N, &Q);
    while(Q--) {
        v = Input();
        if(v == 1) {
            i = Input();
            if(A[i] == 0) Modify(i, 1);
            else Modify(i, -1);
        }
        else {
            L = Input(), R = Input();
            b = Operator(R) - Operator(L-1);
            if(b&1) puts("1");
            else puts("0");
        }  
    }
    return 0;
}