【bzoj1938】ALADIN

  • 本文为博主原创，未经许可不得转载

间问题我们考虑线段树，把区间离散掉

假设线段树上当前被访问的区间是$[l,r]$，要修改的区间是$[L,R]$

区间的和就是$\sum_{x=l}^{r}(x-L+1)\times A\%B$

调整上下界化为$\sum_{x=l-L+1}^{r-L+1}Ax\%B=\sum_{x=l-L+1}^{r-L+1}Ax- B\sum_{x=l-L+1}^{r-L+1}\left \lfloor \frac{Ax}{B} \right \rfloor$

这个和式的值左边是等差数列，右边可以类欧几里得算

那么现在我们只需要维护求和上下界以及A,B的值就可以了

值得注意的是离散化之后，$[mid,mid+1]$之间是有值存在的

我们在划分区间时调整一下就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
using namespace std;
typedef long long ll;
struct event{int L,R,A,B,opt;}eve[MAXN],tree[MAXN<<3];
int tot,hash[MAXN<<1];ll sum[MAXN<<3];
inline int read(){
	int x=0,f=1; char ch=getchar();
	while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
inline int hash_L(int x){return hash[x];}
inline int hash_R(int x){return hash[x+1]-1;}
inline int gcd(int a,int b){return !b?a:gcd(b,a%b);}
inline ll Simgcd(int a,int b,int c,ll n){
	if(!a){
		return b>=c?(n+1):0;
	}
	else if(a>=c||b>=c){
		return 1LL*n*(n+1)/2*(a/c)+1LL*(n+1)*(b/c)+Simgcd(a%c,b%c,c,n);
	}
	else if(a<=c&&b<=c){
		ll m=1LL*(a*n+b)/c;
		return 1LL*n*m-Simgcd(c,c-b-1,a,m-1);
	}
}
inline ll solve(int n,int A,int B){
	int Gcd=gcd(A,B);
	return 1LL*n*(n+1)/2*A-1LL*B*Simgcd(A/Gcd,0,B/Gcd,n);
}
inline void calc(int p){
	int A=tree[p].A,B=tree[p].B;
	sum[p]=solve(tree[p].R,A,B)-solve(tree[p].L-1,A,B);
}
inline void pushdown(int p,int l,int r){
	if(tree[p].B){
		int mid=(l+r)>>1,A=tree[p].A,B=tree[p].B;
		tree[p<<1].A=tree[p<<1|1].A=A;
		tree[p<<1].B=tree[p<<1|1].B=B;
		tree[p<<1].L=tree[p].L;
		tree[p<<1].R=tree[p].L+hash_R(mid)-hash_L(l);
		tree[p<<1|1].L=tree[p].L+hash_L(mid+1)-hash_L(l);
		tree[p<<1|1].R=tree[p].R;
		calc(p<<1); calc(p<<1|1);
	}
	tree[p].B=0;
}
inline void modify(int p,int l,int r,int L,int R,int A,int B){
	if(L<=l&&R>=r){
		tree[p].A=A;
		tree[p].B=B;
		tree[p].L=hash_L(l)-hash_L(L)+1;
		tree[p].R=hash_R(r)-hash_L(L)+1;
		calc(p);
		return;
	}
	int mid=(l+r)>>1; pushdown(p,l,r);
	if(L<=mid)   modify(p<<1,l,mid,L,R,A,B);
	if(R>=mid+1) modify(p<<1|1,mid+1,r,L,R,A,B);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline ll query(int p,int l,int r,int L,int R){
	if(L<=l&&R>=r) return sum[p];
	int mid=(l+r)>>1; pushdown(p,l,r);
	ll ret=0;
	if(L<=mid)   ret+=query(p<<1,l,mid,L,R);
	if(R>=mid+1) ret+=query(p<<1|1,mid+1,r,L,R);
	return ret;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read(),Q=read();
	for(int i=1;i<=Q;++i){
		eve[i].opt=read(); eve[i].L=read(); eve[i].R=read();
		hash[++tot]=eve[i].L; hash[++tot]=eve[i].R+1;
		if(eve[i].opt&1){
			eve[i].A=read();
			eve[i].B=read();
			eve[i].A%=eve[i].B;
		}
	}
	sort(hash+1,hash+tot+1);
	tot=unique(hash+1,hash+tot+1)-hash-1;
	for(int i=1;i<=Q;++i){
		int L=lower_bound(hash+1,hash+tot+1,eve[i].L)-hash;
		int R=lower_bound(hash+1,hash+tot+1,eve[i].R+1)-hash-1;
		if(eve[i].opt&1) modify(1,1,tot,L,R,eve[i].A,eve[i].B);
		else printf("%lld\n",query(1,1,tot,L,R));
	}
	return 0;
}

本文标题:【bzoj1938】ALADIN

文章作者:chty

发布时间:2019年01月20日 - 21时08分

最后更新:2019年01月20日 - 21时15分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,