| Time Limit: 3 second(s) | Memory Limit: 64 MB |
You have an array with n elements which is indexed from 0 to n - 1. Initially all elements are zero. Now you have to deal with two types of operations
1. Increase the numbers between indices i and j (inclusive) by 1. This is represented by the command ‘0 i j‘.
2. Answer how many numbers between indices i and j (inclusive) are divisible by 3. This is represented by the command ‘1 i j‘.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form ‘0 i j‘ or ‘1 i j‘ where i, j are integers and 0 ≤ i ≤ j < n.
Output
For each case, print the case number first. Then for each query in the form ‘1 i j‘, print the desired result.
Sample Input |
Output for Sample Input |
|
1 10 9 0 0 9 0 3 7 0 1 4 1 1 7 0 2 2 1 2 4 1 8 8 0 5 8 1 6 9 |
Case 1: 2 3 0 2 |
Note
Dataset is huge, use faster i/o methods.
题意：0-n-1的数，m次操作，每次有0往区间添加1，和1,询问区间能被3整除的数字个数输出。
思路：之前一直卡TLE。线段树更新区间的话，要用懒标记法，不然会TLE。第一次写有点搓。每个结点存放mod为0，mod为1，mod为2的数字个数，和一个标记v。如果加一，就是把3个数字换一下。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 1000005;
int t, n, Q;
struct Tree {
int l, r, mod0, mod1, mod2, v;
}st[N];
void build(int l, int r, int id) {
if (l != r) {
int mid = (l + r) / 2;
build(l, mid, 2 * id);
build(mid + 1, r, 2 * id + 1);
}
st[id].l = l; st[id].r = r;
if (l == r)
st[id].mod0 = 1;
else
st[id].mod0 = st[id * 2].mod0 + st[id * 2 + 1].mod0;
st[id].mod1 = st[id].mod2 = st[id].v = 0;
}
void tra(Tree &t) {
int t0 = t.mod0, t1 = t.mod1, t2 = t.mod2;
t.mod0 = t2; t.mod1 = t0; t.mod2 = t1;
}
void Insert(int l, int r, int id) {
if (l == st[id].l && r == st[id].r) {
tra(st[id]);
st[id].v++;
return;
}
if (st[id].v) {
int t = st[id].v;
st[id].v = 0;
st[id * 2].v += t;
st[id * 2 + 1].v += t;
t %= 3;
while (t--) {
tra(st[id * 2]);
tra(st[id * 2 + 1]);
}
}
int mid = (st[id].l + st[id].r) / 2;
if (l <= mid && r > mid) {
Insert(l, mid, id * 2);
Insert(mid + 1, r, id * 2 + 1);
}
else if (r <= mid) Insert(l, r, id * 2);
else Insert(l, r, id * 2 + 1);
st[id].mod0 = st[id * 2].mod0 + st[id * 2 + 1].mod0;
st[id].mod1 = st[id * 2].mod1 + st[id * 2 + 1].mod1;
st[id].mod2 = st[id * 2].mod2 + st[id * 2 + 1].mod2;
}
int Query(int l, int r, int id) {
if (l == st[id].l && r == st[id].r) {
return st[id].mod0;
}
if (st[id].v) {
int t = st[id].v;
st[id].v = 0;
st[id * 2].v += t;
st[id * 2 + 1].v += t;
t %= 3;
while (t--) {
tra(st[id * 2]);
tra(st[id * 2 + 1]);
}
}
int mid = (st[id].l + st[id].r) / 2;
if (l <= mid && r > mid) {
return Query(l, mid, id * 2) + Query(mid + 1, r, id * 2 + 1);
}
else if (r <= mid) return Query(l, r, id * 2);
else return Query(l, r, id * 2 + 1);
}
void init() {
memset(st, 0, sizeof(st));
scanf("%d%d", &n, &Q);
build(0, n - 1, 1);
}
void solve() {
int a, b, c;
while (Q--) {
scanf("%d%d%d", &a, &b, &c);
if (a == 0)
Insert(b, c, 1);
else
printf("%d\n", Query(b, c, 1));
}
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
printf("Case %d:\n", ++cas);
init();
solve();
}
return 0;
}