民治营销网站制作,网站不支持m.域名,重庆最新宣传片,wordpress付费阅读全文题目描述 题目来源#xff1a;CQOI 2006 有一个 n 个元素的数组#xff0c;每个元素初始均为 0。有 m 条指令#xff0c;要么让其中一段连续序列数字反转——0 变 1#xff0c;1变 0#xff08;操作 1#xff09;#xff0c;要么询问某个元素的值#xff08;操作 2CQOI 2006 有一个 n 个元素的数组每个元素初始均为 0。有 m 条指令要么让其中一段连续序列数字反转——0 变 11变 0操作 1要么询问某个元素的值操作 2。 例如当 n20 时10 条指令如下 操作回答操作后的数组1 1 10N/A111111111100000000002 61111111111100000000002 120111111111100000000001 5 12N/A111100000011000000002 60111100000011000000002 150111100000011000000001 6 16N/A111101111100111100001 11 17N/A111101111111000010002 121111101111111000010002 61 11110111111100001000 输入格式 第一行包含两个整数 n,m表示数组的长度和指令的条数以下 m行每行的第一个数 t 表示操作的种类 若 t1则接下来有两个数 L,R表示区间 [L,R] 的每个数均反转若 t2则接下来只有一个数 i表示询问的下标。 输出格式 每个操作 2 输出一行非 0 即 1表示每次操作 2 的回答。 样例 样例输入 20 10 1 1 10 2 6 2 12 1 5 12 2 6 2 15 1 6 16 1 11 17 2 12 2 6 样例输出 1 0 0 0 1 1 数据范围与提示 对于 50% 的数据1≤n≤10^3,1≤m≤10^4对于 100% 的数据1≤n≤10^5,1≤m≤5×10^5,保证 L≤R #includecstdio
#includeiostream
#includecstring
#includestring
using namespace std;
const long long maxn100010;
int n, k;
inline void qread(int x){x 0;int ch getchar();while(ch 0 || ch 9) ch getchar();while(ch 0 ch 9) x 10 * x ch - 48, ch getchar();
}
struct BItree{int data[maxn];BItree(){memset(data, 0, sizeof(data));}void add(int x, int v){for(; x n; x (x-x))data[x] v;}int sum(int x){int ans 0;for(; x; x - (x-x))ans data[x];return ans; }
};
int main(void)
{BItree change;qread(n);qread(k);while(k--){int op;qread(op);if(op 1){int y, z;qread(y), qread(z);change.add(y, 1);change.add(z 1, 1);}else{int y;qread(y);printf(%d\n, change.sum(y)1);}}
} 思路 以树状数组统计自1-i数列变化的次数若变化数为奇值为1 否则为0 转载于:https://www.cnblogs.com/junk-yao-blog/p/9471116.html
