Prime Query
Time Limit: 1 Second Memory Limit: 196608 KB
You are given a simple task. Given a sequence A[i] with N numbers. You have to perform Q operations on the given sequence.
Here are the operations:
- A v l, add the value v to element with index l.(1<=V<=1000)
- R a l r, replace all the elements of sequence with index i(l<=i<= r) with a(1<=a<=10^6) .
- Q l r, print the number of elements with index i(l<=i<=r) and A[i] is a prime number
Note that no number in sequence ever will exceed 10^7.
Input
The first line is a signer integer T which is the number of test cases.
For each test case, The first line contains two numbers N and Q (1 <= N, Q <= 100000) - the number of elements in sequence and the number of queries.
The second line contains N numbers - the elements of the sequence.
In next Q lines, each line contains an operation to be performed on the sequence.
Output
For each test case and each query,print the answer in one line.
Sample Input
1
5 10
1 2 3 4 5
A 3 1
Q 1 3
R 5 2 4
A 1 1
Q 1 1
Q 1 2
Q 1 4
A 3 5
Q 5 5
Q 1 5
Sample Output
2
1
2
4
0
4
Author: HUA, Yiwei
题意：维护一个长度为n的序列，有三种操作
A v u 给第u个点增加v的权值
R a l r 把第l到r的元素的权值全部改成a
Q l r 询问第l到r的元素中一共有多少素数
分析：显然的线段树裸题
先线性筛素数，然后维护一下就行
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <deque>
#include <queue>
using namespace std;
typedef long long LL;
typedef double DB;
#define Rep(i, n) for(int i = (0); i < (n); i++)
#define Repn(i, n) for(int i = (n)-1; i >= 0; i--)
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, t, s) for(int i = (t); i >= (s); i--)
#define rep(i, s, t) for(int i = (s); i < (t); i++)
#define repn(i, s, t) for(int i = (s)-1; i >= (t); i--)
#define MIT (2147483647)
#define MLL (1000000000000000000LL)
#define INF (1000000001)
#define mk make_pair
#define ft first
#define sd second
#define clr(x, y) (memset(x, y, sizeof(x)))
#define sqr(x) ((x)*(x))
#define sz(x) ((int) (x).size())
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
inline void SetIO(string Name) {
string Input = Name+".in", Output = Name+".out";
freopen(Input.c_str(), "r", stdin);
freopen(Output.c_str(), "w", stdout);
} const int N = , M = , Max = ;
struct SegTree {
int Tot, Tag, Child[];
#define Tot(x) (Tr[x].Tot)
#define Tag(x) (Tr[x].Tag)
#define Lc(x) (Tr[x].Child[0])
#define Rc(x) (Tr[x].Child[1])
#define Child(x, y) (Tr[x].Child[y])
} Tr[N*M];
int CTr;
int Prime[Max], CPrime;
bool NotPrime[Max];
int n, m, Arr[N]; inline void GetPrime() {
CPrime = ;
For(i, , Max-) {
if(!NotPrime[i]) Prime[++CPrime] = i;
For(j, , CPrime) {
if(1LL*i*Prime[j] >= Max) break;
NotPrime[i*Prime[j]] = ;
if(!(i%Prime[j])) break;
}
}
} inline int Getint() {
int Ret = ;
char Ch = ' ';
while(!(Ch >= '' && Ch <= '')) Ch = getchar();
while(Ch >= '' && Ch <= '') {
Ret = Ret*+Ch-'';
Ch = getchar();
}
return Ret;
} inline void Solve(); inline void Input() {
GetPrime();
int TestNumber;
//scanf("%d", &TestNumber);
TestNumber = Getint();
while(TestNumber--) {
//scanf("%d%d", &n, &m);
n = Getint();
m = Getint();
For(i, , n) scanf("%d", Arr+i);
Solve();
}
} inline void Init() {
CTr = ;
} inline void Updata(int x) {
Tot(x) = ;
Rep(i, )
Tot(x) += Tot(Child(x, i));
} inline void Draw(int x, int Left, int Right, int a) {
if(Left == Right) {
Arr[Left] = a;
Tot(x) = !NotPrime[a];
} else {
Tag(x) = a;
if(NotPrime[a]) Tot(x) = ;
else Tot(x) = Right-Left+;
}
} inline void PushDown(int x, int L, int R) {
if(!Tag(x)) return;
int Mid = (L+R)>>;
Draw(Lc(x), L, Mid, Tag(x));
Draw(Rc(x), Mid+, R, Tag(x));
Tag(x) = ;
} inline void Build(int Left, int Right) {
int Mid = (Left+Right)>>;
int x = ++CTr;
clr(Tr[x].Child, ), Tot(x) = Tag(x) = ;
if(Left == Right) Tot(x) = !NotPrime[Arr[Left]];
else {
Lc(x) = CTr+;
Build(Left, Mid);
Rc(x) = CTr+;
Build(Mid+, Right);
Updata(x);
}
} inline void Add(int x, int Left, int Right, int v, int a) {
int Mid = (Left+Right)>>;
if(Left == Right) {
Arr[v] += a;
Tot(x) = !NotPrime[Arr[v]];
} else {
if(Tag(x)) PushDown(x, Left, Right); if(v <= Mid) Add(Lc(x), Left, Mid, v, a);
else Add(Rc(x), Mid+, Right, v, a);
Updata(x);
}
} inline int Query(int x, int Left, int Right, int L, int R) {
if(Left >= L && Right <= R) return Tot(x);
else {
int Mid = (Left+Right)>>, Ret = ; if(Tag(x)) PushDown(x, Left, Right); if(R <= Mid) Ret = Query(Lc(x), Left, Mid, L, R);
else if(L > Mid) Ret = Query(Rc(x), Mid+, Right, L, R);
else {
Ret = Query(Lc(x), Left, Mid, L, Mid);
Ret += Query(Rc(x), Mid+, Right, Mid+, R);
}
return Ret;
}
} inline void Change(int x, int Left, int Right, int L, int R, int a) {
if(Left >= L && Right <= R) Draw(x, Left, Right, a);
else {
int Mid = (Left+Right)>>; if(Tag(x)) PushDown(x, Left, Right); if(R <= Mid) Change(Lc(x), Left, Mid, L, R, a);
else if(L > Mid) Change(Rc(x), Mid+, Right, L, R, a);
else {
Change(Lc(x), Left, Mid, L, Mid, a);
Change(Rc(x), Mid+, Right, Mid+, R, a);
}
Updata(x);
}
} inline void Solve() {
Init();
Build(, n); char Opt;
int L, R, v, a, Ans;
while(m--) {
for(Opt = ' '; Opt != 'A' && Opt != 'Q' && Opt != 'R'; Opt = getchar()); if(Opt == 'A') {
a = Getint();
v = Getint();
Add(, , n, v, a);
} else if(Opt == 'Q') {
L = Getint();
R = Getint();
Ans = Query(, , n, L, R);
printf("%d\n", Ans);
} else {
a = Getint();
L = Getint();
R = Getint();
Change(, , n, L, R, a);
}
}
} int main() {
Input();
//Solve();
return ;
}