QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115853#4118. 音质检测Hadtsti15 282ms14216kbC++143.7kb2023-06-27 15:35:132023-06-27 15:35:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-27 15:35:15]
  • 评测
  • 测评结果:15
  • 用时:282ms
  • 内存:14216kb
  • [2023-06-27 15:35:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
int n,l,r,nq;
long long a,b,v[300010];
void rd(int &x)
{
	x=0;
	char c=getchar();
	for(;c>'9'||c<'0';c=getchar());
	for(;c<='9'&&c>='0';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
}
void rd(long long &x)
{
	x=0ll;
	char c=getchar();
	for(;c>'9'||c<'0';c=getchar());
	for(;c<='9'&&c>='0';c=getchar())
		x=(x<<3ll)+(x<<1ll)+c-'0';
}
void pt(long long x)
{
	if(x>=10ll)
		pt(x/10ll);
	putchar(x%10ll+'0');
}
struct matrix
{
	int n,m;
	long long a[4][4];
	void init(int k)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(i!=j)
					a[i][j]=0;
				else
					a[i][j]=k;
	}
	friend matrix operator*(matrix a,matrix b)
	{
		matrix c;
		c.n=a.n,c.m=b.m;
		c.init(0);
		for(int i=1;i<=c.n;i++)
			for(int k=1;k<=b.n;k++)
				for(int j=1;j<=c.m;j++)
					(c.a[i][j]+=a.a[i][k]*b.a[k][j]%mod)%=mod;
		return c;
	}
	friend matrix operator+(matrix a,matrix b)
	{
		matrix c;
		c.n=a.n,c.m=a.m;
		c.init(0);
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
		return c;
	}
	friend matrix operator!(matrix a)
	{
		matrix c;
		c.n=a.m,c.m=a.n;
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				c.a[i][j]=a.a[j][i];
		return c;
	}
	friend matrix operator ^(matrix a,long long b)
	{
		matrix c;
		c.n=c.m=a.n,c.init(1);
		for(;b;b>>=1ll)
		{
			if(b&1ll)
				c=c*a;
			a=a*a;
		}
		return c;
	}
}ept,pl,mi,tpl,tmi,f,tf,dm;
long long ni(long long x)
{
	long long res=1ll,b=mod-2;
	for(;b;b>>=1ll)
	{
		if(b&1ll)
			res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
void make(matrix &a)
{
	a.n=3,a.m=3;
}
string op;
struct nd
{
	int l,r;
	matrix s,tl,tr;
}T[1200010];
void pushup(int x)
{
	T[x].s=T[x<<1].s+T[x<<1|1].s;
}
inline void pushdown(int x)
{
	T[x<<1].s=T[x].tl*T[x<<1].s*T[x].tr;
	T[x<<1|1].s=T[x].tl*T[x<<1|1].s*T[x].tr;
	T[x<<1].tl=T[x].tl*T[x<<1].tl;
	T[x<<1|1].tl=T[x].tl*T[x<<1|1].tl;
	T[x<<1].tr=T[x<<1].tr*T[x].tr;
	T[x<<1|1].tr=T[x<<1|1].tr*T[x].tr;
	T[x].tl.init(1),T[x].tr.init(1);
}
void build(int p,int l,int r)
{
	T[p].l=l,T[p].r=r;
	make(T[p].tl),make(T[p].tr);
	T[p].tl.init(1),T[p].tr.init(1);
	if(l==r)
	{
		T[p].s=(pl^(v[l-1]-1))*f;
		T[p].s=T[p].s*tf*(tpl^(v[l+1]-3));
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
void change(int p,int L,int R,matrix lv,matrix rv)
{
	int l=T[p].l,r=T[p].r;
	if(l>R||r<L)
		return;
	if(L<=l&&r<=R)
	{
		T[p].s=lv*T[p].s*rv;
		T[p].tl=lv*T[p].tl;
		T[p].tr=T[p].tr*rv;
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	if(L<=mid)
		change(p<<1,L,R,lv,rv);
	if(R>mid)
		change(p<<1|1,L,R,lv,rv);
	pushup(p);
}
matrix query(int p,int L,int R)
{
	int l=T[p].l,r=T[p].r;
	if(L<=l&&r<=R)
		return T[p].s;
	pushdown(p);
	int mid=l+r>>1;
	matrix res;
	make(res);
	res.init(0);
	if(R>mid)
		res=query(p<<1|1,L,R);
	if(L<=mid)
		res=res+query(p<<1,L,R);
	return res;
}
int main()
{
	rd(n),rd(nq),rd(a),rd(b);
	for(int i=1;i<=n;i++)
		rd(v[i]);
	make(pl),make(f);
	make(mi),make(ept),make(dm);
	ept.init(0),dm.init(1);
	pl.a[1][1]=pl.a[2][1]=pl.a[3][3]=1;
	pl.a[1][2]=a;
	pl.a[1][3]=b;
	f.a[1][1]=2;
	f.a[2][1]=f.a[3][1]=1;
	tpl=!pl;
	tf=!f;
	if(a)
	{
		mi.a[1][2]=mi.a[3][3]=1;
		mi.a[2][1]=ni(a);
		mi.a[2][2]=mod-ni(a);
		mi.a[2][3]=mod-b*ni(a)%mod;
	}
	else
	{
		mi.a[1][2]=mi.a[2][2]=mi.a[3][3]=1;
		mi.a[2][3]=mod-b;
	}
	tmi=!mi;
	build(1,2,n-1);
	while(nq--)
	{
		cin>>op>>l>>r;
		if(op=="plus")
			change(1,l+1,r+1,pl,dm),change(1,l-1,r-1,dm,tpl);
		else if(op=="minus")
			change(1,l+1,r+1,mi,dm),change(1,l-1,r-1,dm,tmi); 
		else if(op=="query")
			pt(query(1,l+1,r-1).a[1][1]),putchar('\n');
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 153ms
memory: 12688kb

input:

5000 5000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...

output:

30754429
194963785
423087280
568458582
919326931
359004807
861904941
755570340
168436553
373953894
923437580
934015038
585341183
155788638
614511929
116977240
234560163
60030009
118673746
628651237
615800005
308768153
695314874
853373610
496333245
412967503
206869522
856983328
9608271
941717977
6872...

result:

ok 2057 lines

Test #2:

score: 5
Accepted
time: 252ms
memory: 14216kb

input:

7000 7000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...

output:

699552387
116711244
257075385
500055273
63374553
90503904
549081160
162409060
51202676
211756813
786311151
49255389
876981955
909107987
835214464
143761702
376141766
578393672
364811199
708437438
15462795
403930144
938168704
251680630
167431629
229107418
203033028
153135539
315236576
341269317
62012...

result:

ok 2771 lines

Test #3:

score: 5
Accepted
time: 282ms
memory: 14040kb

input:

8000 8000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...

output:

364216242
33589407
13036783
289758383
751963601
304836331
441157937
116807134
470264951
877456989
408962375
260881052
254546045
856816319
528760090
771670173
484913701
886579595
323359736
147054683
255504035
717899331
456158394
361180578
634404961
957834998
891216116
346677655
831971764
650152480
52...

result:

ok 3197 lines

Test #4:

score: 0
Time Limit Exceeded

input:

200000 8000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 1900...

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

250000 9000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 1900...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

300000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

200000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

230000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

250000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

270000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #11:

score: 0
Time Limit Exceeded

input:

290000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #12:

score: 0
Time Limit Exceeded

input:

300000 10000
0 1
1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...

output:


result:


Test #13:

score: 0
Time Limit Exceeded

input:

250000 10000
0 628547775
1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 ...

output:


result:


Test #14:

score: 0
Time Limit Exceeded

input:

300000 10000
0 628547775
1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 ...

output:


result:


Test #15:

score: 0
Time Limit Exceeded

input:

250000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

260000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

270000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

280000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

290000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

300000 10000
628547775 786481517
1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...

output:


result: