雷顿女士与选书

第一行输入一个T( $1\leq T \leq10$ )表示数据组数。

接下来T组数据。

对于每组数据，第一行输入n，m( $1 \leq n,m \leq 10^4$ )，分别表示图书馆的数量和时刻的数量。

接下来有m行，每行输入1，pos，x( $1 \leq pos \leq n,1 \leq x \leq 100$ )或者2，l，r，k( $1 \leq l \leq r \leq n,1 \leq k \leq 10$ )。

C++11(clang++ 3.9) 解法, 执行用时: 651ms, 内存消耗: 2536K, 提交时间: 2019-12-08 15:45:15

#include<bits/stdc++.h>

using namespace std;
const int mod=1e9+7;
const int maxn=1e4+5;
int t,n,m;
struct node{
	int num[11];
	node(){
		memset(num,0,sizeof(num));
	}
	node operator+(const node&a)const{
		node p;
		for (int i=0;i<=10;i++)
			for (int j=0;j<=10-i;j++){
				if (i+j>10) continue;
				p.num[i+j]=(p.num[i+j]+1ll*num[i]*a.num[j]%mod)%mod;
			}
		return p;
	}
}tree[maxn<<2];
void build(int l,int r,int k){
	if (l==r){
		tree[k]=node();
		tree[k].num[0]=1;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,k*2);
	build(mid+1,r,k*2+1);
	tree[k]=tree[k*2]+tree[k*2+1];
}
int cnt[maxn];
void update(int pos,int l,int r,int k,int c){
	if (pos<l||pos>r) return;
	if (l==r){
		tree[k].num[1]=cnt[l];
		return;
	}
	int mid=l+r>>1;
	update(pos,l,mid,k*2,c);
	update(pos,mid+1,r,k*2+1,c);
	tree[k]=tree[k*2]+tree[k*2+1];
}
node E;
node query(int L,int R,int l,int r,int k){
	if (l>R||L>r) return E;
	if (L<=l&&R>=r)	return tree[k];
	int mid=l+r>>1;
	return query(L,R,l,mid,k*2)+query(L,R,mid+1,r,k*2+1);
}
int main(){
	scanf("%d",&t);
	E.num[0]=1;
	while (t--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
			cnt[i]=0;
		build(1,n,1);
		for (int i=1,op,pos,x,l,r,k;i<=m;i++){
			scanf("%d",&op);
			if (op==1){
				scanf("%d%d",&pos,&x);
				cnt[pos]+=x;
				update(pos,1,n,1,x);
			}else{
				scanf("%d%d%d",&l,&r,&k);
				node u = query(l,r,1,n,1);
				cout << u.num[k] << '\n';
			}
		}
	}
}

详情