2011-05-29 07:53:28Morris
a048. 函数增减性
http://zerojudge.tw/ShowProblem?problemid=a048
內容 ：
单调函数的增减性的判断想必大家都很清楚了吧...
这里有N个函数f1(x),f2(x),…,fN(x)，开始时我告诉你他们全都是增函数。由于我记性不好，我会时不时发现哪个函数的增减性我说错了，要进行更改。当然，更改的话，肯定告诉你不是增（减）函数而是减（增）函数。
这里，我们定义一个函数F(x)=fL(fL+1(…fR(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)=fL(fL+1(…fR(x)…))的增减性。
輸出說明
：
对所有v=2的操作，输出F(x)的增减性。
若F(x)是增函数则输出0，若F(x)是减函数则输出1。
範例輸入 ：
5 3 2 2 4 1 3 2 2 4
範例輸出 ：
0 1
提示
：
测资可能有误，欢迎推翻！
出處
：
liouzhou_101
(管理：liouzhou_101)
題目有點難懂就是了，還好請了別人來幫我看看 ...
作法 : Binary indexed tree
你可以用微分發現(連鎖定理)
F(x)=fL(fL+1(…fR(x)…))
F'(x)= fL ' (fL+1(…fR(x)…)) * (fL+1'(…fR(x)…)) ...
只要查看減函數在[L,R]中的個數，就可以判定了
題目有點難懂就是了，還好請了別人來幫我看看 ...
作法 : Binary indexed tree
你可以用微分發現(連鎖定理)
F(x)=fL(fL+1(…fR(x)…))
F'(x)= fL ' (fL+1(…fR(x)…)) * (fL+1'(…fR(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;
}
上一篇：d872. 過橋問題
下一篇：a058. MOD3