样例最后两次询问不对求助
查看原帖
样例最后两次询问不对求助
521283
wangif424楼主2024/7/4 20:24
#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
constexpr int mod=1e9+7;
struct jz{
	int a[3][3];
	jz(){
		a[0][0]=a[0][1]=a[0][2]=0;
		a[1][0]=a[1][1]=a[1][2]=0;
		a[2][0]=a[2][1]=a[2][2]=0;
	}
	jz(int n){
		a[0][1]=a[0][2]=0;
		a[1][0]=a[1][2]=0;
		a[2][0]=a[2][1]=0;
		a[0][0]=a[1][1]=a[2][2]=1;
	}
	jz(int a00,int a01,int a02,
	   int a10,int a11,int a12,
	   int a20,int a21,int a22){
		a[0][0]=a00;a[0][1]=a01;a[0][2]=a02;
		a[1][0]=a10;a[1][1]=a11;a[1][2]=a12;
		a[2][0]=a20;a[2][1]=a21;a[2][2]=a22;
	}
	int*operator[](int i){
		return a[i];
	}
	jz operator+(jz b)const{
		return jz((a[0][0]+b[0][0])%mod,(a[0][1]+b[0][1])%mod,(a[0][2]+b[0][2])%mod,
		(a[1][0]+b[1][0])%mod,(a[1][1]+b[1][1])%mod,(a[1][2]+b[1][2])%mod,
		(a[2][0]+b[2][0])%mod,(a[2][1]+b[2][1])%mod,(a[2][2]+b[2][2])%mod);
	}
	jz operator*(jz b)const{
		jz c;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
				}
			}
		}
		return c;
	}
	jz operator=(int n){
		return jz(1);
	}
	jz operator%(int n)const{
		jz c=*this;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)c[i][j]%=mod;
		return c;
	}
	void out(){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++)cerr << a[i][j] << ' ';
			cerr << '\n';
		}
	}
}tpl,tmi,mi,pl;
int n,q,a,b,f0;
void out(int n){
	return;
}
void out(jz n){
	n.out();
}
template<typename T>
T qpow(T a,int n){
	T r=1;
	while(n){
		if(n&1)r=r*a%mod;
		n>>=1;
		a=a*a%mod;
	}
	return r;
}
int A[300100];
struct tree{
	int ls,rs;
	jz l1,l2,s;
}t[600100];
int siz=1;
void build(int i,int l,int r){
	t[i].l1=jz(1);
	t[i].l2=jz(1);
	if(l==r){
		t[i].s=qpow(tpl,A[l+1]-3)*jz(2,0,0,1,0,0,1,0,0)*jz(2,1,1,0,0,0,0,0,0)*qpow(pl,A[l-1]-1);
		return;
	}
	int mid=(l+r)>>1;
	t[i].ls=++siz;
	t[i].rs=++siz;
	build(t[i].ls,l,mid);
	build(t[i].rs,mid+1,r);
	t[i].s=t[t[i].ls].s+t[t[i].rs].s;
}
void pd(int i){
	t[t[i].ls].s=t[t[i].ls].s*t[i].l1;
	t[t[i].rs].s=t[t[i].rs].s*t[i].l1;
	t[t[i].ls].l1=t[t[i].ls].l1*t[i].l1;
	t[t[i].rs].l1=t[t[i].rs].l1*t[i].l1;
	t[i].l1=1;
	t[t[i].ls].s=t[i].l2*t[t[i].ls].s;
	t[t[i].rs].s=t[i].l2*t[t[i].rs].s;
	t[t[i].ls].l2=t[i].l2*t[t[i].ls].l2;
	t[t[i].rs].l2=t[i].l2*t[t[i].rs].l2;
	t[i].l2=1;
}
void upd(int i,int l,int r,int ll,int rr,jz k1,jz k2){
	if(l>rr||r<ll)return;
	cerr << ll << ' ' <<rr << '\n';
	if(ll<=l&&r<=rr){
		t[i].s=t[i].s*k1;
		t[i].l1=t[i].l1*k1;
		t[i].s=k2*t[i].s;
		t[i].l2=k2*t[i].l2;
		return;
	}
	pd(i);
	int mid=(l+r)>>1;
	if(ll<=mid)upd(t[i].ls,l,mid,ll,rr,k1,k2);
	if(rr>mid)upd(t[i].rs,mid+1,r,ll,rr,k1,k2);
	t[i].s=t[t[i].ls].s+t[t[i].rs].s;
}
void Plus(int l,int r){
	upd(1,2,n-1,l+1,r+1,jz(1),pl);
	upd(1,2,n-1,l-1,r-1,tpl,jz(1));
}
void Minus(int l,int r){
	upd(1,2,n-1,l+1,r+1,jz(1),mi);
	upd(1,2,n-1,l-1,r-1,tmi,jz(1));
}
jz query(int i,int l,int r,int ll,int rr){
	if(ll<=l&&r<=rr)return t[i].s;
	pd(i);
	int mid=(l+r)>>1;
	jz s;
	s=jz();
	if(ll<=mid)s=s+query(t[i].ls,l,mid,ll,rr);
	if(rr>mid)s=s+query(t[i].rs,mid+1,r,ll,rr);
	return s;
}
signed main(){
	R(n);R(q);
	R(a);R(b);
	f0=(1-b+mod)*qpow(a,mod-2)%mod;
	for(int i=1;i<=n;i++)R(A[i]);
	pl=jz(1,1,0,a,0,0,b,0,1);
	tpl=jz(1,a,b,1,0,0,0,0,1);
	if(a)mi=(0,qpow(a,mod-2),0,1,mod-qpow(a,mod-2),0,0,mod-b*qpow(a,mod-2),1);
	else mi=(0,0,0,1,1,0,0,mod-b,1);
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			tmi[i][j]=mi[j][i];
		}
	}
	build(1,2,n-1);
	while(q--){
		string opt;
		int l,r;
		cin >> opt;
		R(l);R(r);
		if(opt=="query"){
			write(query(1,2,n-1,l+1,r-1)[0][0]);
			push('\n');
		}else if(opt=="minus"){
			Minus(l,r);
		}else{
			Plus(l,r);
		}
	}
    return 0;
}

2024/7/4 20:24
加载中...