2015
04-14

# Play With Sequence

When the girl was solving GSSX, a serious of tough problems about data structure on SPOJ, something intriguing once again comes to GYZ’s mind. That is, for a changing sequences, how to count how many elements in a specific range efficiently.

Without any beneficial idea, as usual, GYZ asks her friend, CLJ for help. But this time, unfortunately, CLJ is playing a gal-game at present, does not have sparse time.

So now , it is your turn…

Cause the original problem is not as easy as first glance, let’s examine a simplified one:

you are given a sequence A[1], A[2],…, A[N]. On this sequence you have to apply M operations: Add all the elements whose value are in range [l, r] with d or, ask for a query how many element are in range [l, r].

There are only one test case, Process until the end of the file. The first line of each case contains two numbers, N, M, described as above. And then start from the second line, have N numbers described the sequence’s initial value.

( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]|≤ 1,000,000,000 .)

The following M lines described the operation:

C l r d: Add all the element whose value are in range [l, r] with d. (Redeclare: Not its Position! .. ) Q l r: ask for a query how many elements, whose value are in range [l, r].

( l ≤ r, |l|,|r|,|d|≤ 1,000,000,000 )

We guarantee every elements are suits 32-integer, and will not cause overflow, even during the running-time. (.. but still be careful ;) Besides, all the test-data are generated randomly.

There are only one test case, Process until the end of the file. The first line of each case contains two numbers, N, M, described as above. And then start from the second line, have N numbers described the sequence’s initial value.

( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]|≤ 1,000,000,000 .)

The following M lines described the operation:

C l r d: Add all the element whose value are in range [l, r] with d. (Redeclare: Not its Position! .. ) Q l r: ask for a query how many elements, whose value are in range [l, r].

( l ≤ r, |l|,|r|,|d|≤ 1,000,000,000 )

We guarantee every elements are suits 32-integer, and will not cause overflow, even during the running-time. (.. but still be careful ;) Besides, all the test-data are generated randomly.

10 10
10 4 -5 8 8 3 0 -2 4 7
C -9 8 2
C -4 10 -3
C -10 0 5
Q -9 -1
C -9 -5 8
C -7 4 3
Q -2 7
C -10 -3 2
C -4 -1 -6
Q 7 10

1
10
4

Hint(In the first example, after the two operations, the sequences are become to, {-4, -3, -2, -1, 0, 11, 12, 13, 14, 15},
so there are no elements whose value are in range [1, 10]. )  

http://acm.hdu.edu.cn/showproblem.php?pid=3971

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

namespace ST
{
typedef long long LL;
const int maxn = 300010;
LL a[maxn];

inline void pushUp(int rt)
{
Max[rt] = max(Max[rt<<1], Max[rt<<1|1]);
Min[rt] = min(Min[rt<<1], Min[rt<<1|1]);
}

inline void modify(int rt, LL c)
{
Max[rt] += c;
Min[rt] += c;
}

inline void pushDown(int rt)
{
modify((rt << 1) | 1, add[rt]);
}

void build(int l, int r, int rt)
{
if (l == r) {
Max[rt] = Min[rt] = a[l];
return ;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, (rt << 1) | 1);
pushUp(rt);
}

void update(int l, int r, int rt, LL L, LL R, LL D)
{
if (L > Max[rt] || R < Min[rt]) return ;
if (L <= Min[rt] && R >= Max[rt]) {
modify(rt, D);
return ;
}
if (l == r) return ;
int m = (l + r) >> 1;
pushDown(rt);
update(l, m, rt << 1, L, R, D);
update(m + 1, r, (rt << 1) | 1, L, R, D);
pushUp(rt);
}

int query(int l, int r, int rt, LL L, LL R)
{
if (L > Max[rt] || R < Min[rt]) {
return 0;
}
if (L <= Min[rt] && R >= Max[rt]) {
return r - l + 1;
}
if (l == r) return 0;
int m = (l + r) >> 1;
pushDown(rt);
return query(l, m, rt << 1, L, R) + query(m + 1, r, (rt << 1) | 1, L, R);
}

void getNewArr(int l, int r, int rt)
{
if (l == r) {
a[l] = Max[rt];
return ;
}
int m = (l + r) >> 1;
pushDown(rt);
getNewArr(l, m, rt << 1);
getNewArr(m + 1, r, (rt << 1) | 1);
}
}

int main()
{
using namespace ST;
int n, m;
char op[2];
long long L, R, D;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1);
build(1, n, 1);
while (m--) {
scanf("%s", op);
if (op[0] == 'C') {
scanf("%lld%lld%lld", &L, &R, &D);
update(1, n, 1, L, R, D);
} else {
scanf("%lld%lld", &L, &R);
printf("%d\n", query(1, n, 1, L, R));
}
if (m % 4500 == 0) {
getNewArr(1, n, 1);
sort(a + 1, a + n + 1);
build(1, n, 1);
}
}
}
return 0;
}


1. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}