给定 \(n\times n\) 的黑白方格，期初所有颜色均为白色，支持以下操作
- 翻转 \([l,r]\) 行/列的颜色
- 翻转质数/合数 行/列的颜色
- 求 \([l1,r1]\) 行、 \([l2,r2]\) 列围成的区域内的所有方格中黑色方格的数量。
\(n\leq 10^5,m\leq 2\times 10^5\) 。
首先需要明确的是，本题中行列并不互相干扰，因为1,2两种操作都只会单独对行或列造成干扰，而若求出 \([l1,r1]\) 之间的被翻转成黑色的行数 \(ans1\) ， \([l2,r2]\) 之间被翻转的列数 \(ans2\) ，那么答案就是
\[ans1\times(r2-l2+1)+ans2\times(r1-l1+1)-2\times ans1\times ans2 \]知道这一点，我们就可以用数据结构来分别维护行和列。那么现在棘手的问题是如何处理质数和合数。
首先，1是要特殊考虑的，所以可以直接维护2个变量来存储第一行和第一列，其次考虑用线段树来维护序列。
定义以下变量到每个线段树的节点： \(p,r\) 分别表示区间内的质数数量和合数数量， \(psum,rsum\) 分别表示区间内被涂黑的质数个数和合数个数。同时，在合并时只需要将对应量相加即可。然后谈修改，每次修改都是将原先白的变成黑的，所以
\[psum=p-psum,rsum=r-rsum \]即可，在修改时记录2个懒标记，分别对应 \(p\) 和 \(r\) 。那么，修改操作就可以用4元组来表示 \((l,r,pp,rr)\) 表示在 \([l,r]\) 区间内翻转/不翻转 \(p,r\) 所以操作1就是 \((l,r,1,1)\) ，操作2就是 \((1,n,0/1,0/1)\) 。
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define chkmin(_A,_B) (_A=min(_A,_B))
#define chkmax(_A,_B) (_A=max(_A,_B))
using std::max;
using std::min;
//--------------------FastInOut--------------------//
class IO{
public:
inline char read(){
static const int IN_LEN =1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
}
template<typename _Tp>inline IO &operator >>(_Tp &x){
static char c11, boo;
for (c11=read(),boo=0;!isdigit(c11);c11=read()) {
if (c11==-1)
return *this;
boo|=(c11=='-');
}
for(x=0;isdigit(c11);c11=read())
x=x*10+(c11^'0');
if(boo)
x=-x;
return *this;
}
inline void push(const char &c) {
putchar(c);
}
template<typename _Tp>inline IO &operator <<( _Tp x){
if (x<0)
x=-x,push('-');
static _Tp sta[35];
_Tp top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top)
push(sta[--top]+'0');
return *this;
}
inline IO &operator <<(char lastChar){
push(lastChar);
return *this;
}
}FIO;
int n,m;
int P[100005];
struct info{
int p,r;
int psum,rsum;
info(int x=0){
if(x==0)
p=r=psum=rsum=0;
else if(P[x]==0)
p=1,psum=rsum=r=0;
else
r=1,psum=rsum=p=0;
}
friend info operator +(const info &A,const info &B){
info ret;
ret.psum=A.psum+B.psum;
ret.rsum=A.rsum+B.rsum;
ret.p=A.p+B.p;
ret.r=A.r+B.r;
return ret;
}
};
struct SegmentTree{
struct node{
int tagp,tagr;
info I;
}nd[400005];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
void pushup(const int &p){
nd[p].I=nd[ls(p)].I+nd[rs(p)].I;
}
void addtag(const int &p,const int &pp,const int &rr){
if(pp==1){
nd[p].tagp^=1;
nd[p].I.psum=nd[p].I.p-nd[p].I.psum;
}
if(rr==1){
nd[p].tagr^=1;
nd[p].I.rsum=nd[p].I.r-nd[p].I.rsum;
}
}
void pushdown(const int &p){
if(nd[p].tagr+nd[p].tagp!=0){
addtag(ls(p),nd[p].tagp,nd[p].tagr);
addtag(rs(p),nd[p].tagp,nd[p].tagr);
nd[p].tagp=nd[p].tagr=0;
}
}
void build(const int &l,const int &r,const int &p){
if(l==r){
nd[p].I=info(l);
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
pushup(p);
}
void change(const int &l,const int &r,const int &ql,const int &qr,const int &p,const int &pp,const int &rr){
if(ql<=l && r<=qr){
addtag(p,pp,rr);
return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(ql<=mid)
change(l,mid,ql,qr,ls(p),pp,rr);
if(qr>mid)
change(mid+1,r,ql,qr,rs(p),pp,rr);
pushup(p);
}
info getsum(const int &l,const int &r,const int &ql,const int &qr,const int &p){
if(ql<=l && r<=qr)
return nd[p].I;
pushdown(p);
int mid=(l+r)>>1;
info gl,gr;
if(ql<=mid)
gl=getsum(l,mid,ql,qr,ls(p));
if(qr>mid)
gr=getsum(mid+1,r,ql,qr,rs(p));
return gl+gr;
}
}R,C;
int R1,C1;
int main(){
FIO>>n>>m;
for(int i=2;i<=n;++i){
if(P[i]==0){
for(int j=2;i*j<=n;++j){
P[i*j]=1;
}
}
}
R.build(2,n,1);
C.build(2,n,1);
while(m--){
char c=FIO.read();
while(c!='N' && c!='M' && c!='Q' && c!='P' && c!='R'){
c=FIO.read();
}
if(c=='M'){
int l,r;
FIO>>l>>r;
R.change(2,n,max(2,l),r,1,1,1);
if(l==1)
R1^=1;
}
if(c=='N'){
int l,r;
FIO>>l>>r;
C.change(2,n,max(2,l),r,1,1,1);
if(l==1)
C1^=1;
}
if(c=='P'){
int v;
FIO>>v;
if(v==0){
R.change(2,n,2,n,1,1,0);
}
else{
C.change(2,n,2,n,1,1,0);
}
}
if(c=='R'){
int v;
FIO>>v;
if(v==0){
R.change(2,n,2,n,1,0,1);
}
else{
C.change(2,n,2,n,1,0,1);
}
}
if(c=='Q'){
ll l1,l2,r1,r2;
FIO>>l1>>r1>>l2>>r2;
info g1=R.getsum(2,n,max(l1,2ll),r1,1);
ll ans1=g1.psum+g1.rsum+((l1==1)?R1:0);
info g2=C.getsum(2,n,max(l2,2ll),r2,1);
ll ans2=g2.psum+g2.rsum+((l2==1)?C1:0);
FIO<<ans1*(r2-l2+1)+ans2*(r1-l1+1)-2ll*ans1*ans2<<'\n';
}
}
return 0;
}