列表

详情

NC17694. Rikka with Prefix Sum

描述

Prefix Sum is a useful trick in data structure problems.

For example, given an array A of length n and m queries. Each query gives an interval [l,r] and you need to calculate . How to solve this problem in O(n+m)? We can calculate the prefix sum array B in which Bi is equal to . And for each query, the answer is Br-Bl-1.

Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you:

Given two integers n,m, Rikka constructs an array A of length n which is initialized by Ai = 0. And then she makes m operations on it.

There are three types of operations:
1. 1 L R w, for each index i ∈ [L,R], change Ai to Ai + w.
2. 2, change A to its prefix sum array. i.e., let A' be a back-up of A, for each i ∈ [1,n], change Ai to .
3. 3 L R, query for the interval sum .

输入描述

The first line contains a single number t(1≤ t ≤ 3), the number of the testcases.

For each testcase, the first line contains two integers n,m(1 ≤ n,m ≤ 105). 

And then m lines follow, each line describes an operation(1 ≤ L ≤ R≤ n, 0 ≤ w ≤ 109). 

The input guarantees that for each testcase, there are at most 500 operations of type 3.

输出描述

For each query, output a single line with a single integer, the answer modulo 998244353.

示例1

输入: 

1
100000 7
1 1 3 1
2
3 2333 6666
2
3 2333 6666
2
3 2333 6666

输出: 

13002
58489497
12043005

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1048ms, 内存消耗: 7488K, 提交时间: 2018-08-24 16:25:32 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=998244353;
ll fac[2*N+5],inv[2*N+5];
struct node{
	int x,w,t;
}s[2*N];
int cnt;
int t;

ll fpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

ll C(int n,int m)
{
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

void init(int n)
{
	fac[0]=1;
	for(int i=1; i<=n; i++)
		fac[i]=i*fac[i-1]%mod;
	inv[n]=fpow(fac[n],mod-2);
	for(int i=n-1; i>=0; i--)
		inv[i]=inv[i+1]*(i+1)%mod;
}

ll query(int x,int now)
{
	ll ans=0;
	for(int i=0; i<cnt; i++)
		if(s[i].x<=x)
			ans=(ans+C(now-s[i].t+x-s[i].x,x-s[i].x)*s[i].w)%mod;
	return ans;
}

void solve()
{
	int op,n,m;
	int l,r,w;
	cin>>n>>m;
	cnt=0;
	t=0;
	for(int i=0; i<m; i++)
	{
		scanf("%d",&op);
		if(op==2)
			t++;
		else if(op==1)
		{
			scanf("%d%d%d",&l,&r,&w);
			s[cnt++]=(node){l,w%mod,t};
			s[cnt++]=(node){r+1,(mod-w)%mod,t};
		}
		else
		{
			scanf("%d%d",&l,&r);
			printf("%lld\n",(query(r,t+1)-query(l-1,t+1)+mod)%mod);
		}
	}
}

int main()
{
	int T;
	init(2*N);
	cin>>T;
	while(T--)
		solve();
	return 0;
}

C++(clang++11) 解法, 执行用时: 653ms, 内存消耗: 13816K, 提交时间: 2020-11-21 15:47:16 

#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
const int maxn=1e6+100;
typedef long long ll;
const int M=998244353;
struct node{
	int x,y,v;
};
vector<node> a;
int inv[maxn],nf[maxn],f[maxn],n,cur,q;
int F(int x,int y){return 1ll*f[x+y]*nf[x]%M*nf[y]%M;}
int qry(int x){
	int res=0;
	for (auto p:a) if (p.y<=x){
		int cof=F(cur+1-p.x,x-p.y);
		res=(res+1ll*cof*p.v)%M;	
	}
	return res;
}
int main(){
	inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
	f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
	int _; scanf("%d",&_);
	while (_--){
		a.clear();
		cur=1;
		scanf("%d%d",&n,&q);
		while (q--){
			int op;scanf("%d",&op);
			if (op==1){
				int l,r,w;scanf("%d%d%d",&l,&r,&w); w%=M;
				a.pb((node){cur,l,w});
				a.pb((node){cur,r+1,M-w});
			} else if (op==2){
				cur++;
			} else {
				int l,r; scanf("%d%d",&l,&r);
				printf("%d\n",(qry(r)-qry(l-1)+M)%M);
			}
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com