2 条题解

  • 0
    @ 2026-2-21 21:30:35

    题解：P4433 [COCI 2009/2010 #1] ALADIN

    这题真ex调了我两天

    首先这题是一道区间赋值及查询区间和，特殊的就是区间赋值是加上一个等差数列并取模，即需要计算

    ∑i=LR(A×imod  B)\sum_{i=L}^{R}(A\times i\mod B)

    首先可以看作

    $$\sum_{i=0}^{R}(A\times i\mod B)-\sum_{i=0}^{L-1}(A\times i\mod B)$$

    即只需要计算

    ∑i=0N(A×imod  B)\sum_{i=0}^{N}(A\times i\mod B)

    注意到这个取模非常烦，想一下怎么把取模去掉，注意到 amod  ba\mod b 等价于 a−b×⌊ab⌋a-b\times⌊\frac{a}{b}⌋，所以上式可以转化为

    $$\sum_{i=0}^{N}(A\times i-B\times⌊\frac{A\times i}{B}⌋)$$

    接下来就比较简单了，把前面 A×iA\times i 的部分提出来，后面的 −B-B 提出

    $$\frac{N(N+1)}{2}A-B\sum_{i=0}^{N}⌊\frac{A\times i}{B}⌋$$

    后面的 ∑i=0N⌊A×iB⌋\sum_{i=0}^{N}⌊\frac{A\times i}{B}⌋ 就是类欧板子，直接用类欧即可（相当于 f(A,0,B,N)f(A,0,B,N)）（不会类欧的出门右转P5170 【模板】类欧几里德算法）

    注意

    1，开 long long

    2，不要用动态开点，会MLE，用离散化

    3，离散化要把每次询问的 L,R,L−1,R−1,L+1,R+1L,R,L-1,R-1,L+1,R+1 全部记录，并且线段树记录的是 lsh[l]∽lsh[r+1]−1lsh[l]\backsim lsh[r+1]-1 这一段，不是 lsh[l]∽lsh[r]lsh[l]\backsim lsh[r]。

    代码

    #include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
typedef long long ll;
int n,q,id;
ll calc(ll a,ll b,ll c,ll n){//类欧 
	if(a==0)return b/c*(n+1);
	if(n==0)return b/c;
	if(a>=c||b>=c){
		ll s=calc(a%c,b%c,c,n);
		return s+n*(n+1)/2*(a/c)+(n+1)*(b/c);
	}
	ll m=(a*n+b)/c;
	ll s=calc(c,c-b-1,a,m-1);
	return n*m-s;
}
ll get(ll n,ll a,ll b){//计算$\sum_{i=0}^{N}(A\times i\mod B)$
	return n*(n+1)/2*a-b*calc(a,0,b,n);
}
struct Q{
	int op;
	ll l,r,a,b;
}qq[50010];//记录操作 
ll lsh[300010];//离散化数组 
struct N{//线段树 
	ll c,l,a,b;
}tr[1200010];
void pushup(int p){
	tr[p].c=tr[lc(p)].c+tr[rc(p)].c;
}
void bt(int p,int l,int r){
	if(l==r){
		tr[p]={0,0,0,0};
		return ;
	}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);
	bt(rc(p),mid+1,r);
}
void pushdown(int p,int l,int r){
	if(tr[p].l){
		int mid=(l+r)>>1;
		tr[lc(p)].c=get(lsh[mid+1]-1-tr[p].l+1,tr[p].a,tr[p].b)-get(lsh[l]-tr[p].l,tr[p].a,tr[p].b);//注意不要忘了lsh数组 
		tr[rc(p)].c=get(lsh[r+1]-1-tr[p].l+1,tr[p].a,tr[p].b)-get(lsh[mid+1]-tr[p].l,tr[p].a,tr[p].b);
		tr[lc(p)].l=tr[rc(p)].l=tr[p].l;
		tr[lc(p)].a=tr[rc(p)].a=tr[p].a;
		tr[lc(p)].b=tr[rc(p)].b=tr[p].b;
		tr[p].l=tr[p].a=tr[p].b=0;
	}
}
void change(int p,int l,int r,int x,int y,ll a,ll b){
	if(l>=x&&r<=y){
		tr[p].c=get(lsh[r+1]-1-lsh[x]+1,a,b)-get(lsh[l]-lsh[x],a,b);
		tr[p].l=lsh[x];tr[p].a=a;tr[p].b=b;
		return ;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(p),l,mid,x,y,a,b);
	if(y>mid)change(rc(p),mid+1,r,x,y,a,b);
	pushup(p);
}
ll find(int p,int l,int r,int x,int y){
	if(l>=x&&r<=y)return tr[p].c;
	pushdown(p,l,r); 
	int mid=(l+r)>>1;
	ll ans=0;
	if(x<=mid)ans+=find(lc(p),l,mid,x,y);
	if(y>mid)ans+=find(rc(p),mid+1,r,x,y);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>qq[i].op;
		if(qq[i].op==1)cin>>qq[i].l>>qq[i].r>>qq[i].a>>qq[i].b;
		else cin>>qq[i].l>>qq[i].r;
		lsh[i]=qq[i].l;lsh[i+q]=qq[i].r;
		lsh[i+q*2]=qq[i].l-1;lsh[i+q*3]=qq[i].r+1; 
		lsh[i+q*4]=qq[i].l+1;lsh[i+q*5]=qq[i].r-1; 
	}
	sort(lsh+1,lsh+1+q*6);
	int ln=unique(lsh+1,lsh+1+q*6)-lsh-1;
	bt(1,1,ln); 
	for(int i=1;i<=q;i++){
		qq[i].l=lower_bound(lsh+1,lsh+1+ln,qq[i].l)-lsh;
		qq[i].r=lower_bound(lsh+1,lsh+1+ln,qq[i].r)-lsh;
		if(qq[i].op==1)change(1,1,ln,qq[i].l,qq[i].r,qq[i].a,qq[i].b);
		else cout<<find(1,1,ln,qq[i].l,qq[i].r)<<'\n';
	}
	return 0;
}
    • 0
      @ 2026-2-6 0:44:42

      P4433

      cnblogs

      Problem

      有一个长度为 nn 初始所有元素均为为 00 的数列 aa。

      要求支持两种操作：

      • 给定 L,R,A,BL, R, A, B，表示对于 ∀i∈[L,R]\forall i\in [L, R]，ai←(A×(i−L+1)) mod Ba_i \gets (A\times (i - L + 1)) \bmod B。

      • 给定 L,RL, R，输出 ∑i=LRai\sum\limits_{i = L}^{R} a_i。

      1≤n≤109,1≤q≤5×1041\le n\le 10^9, 1\le q\le 5\times 10^4。

      时空限制：8s, 64MB。

      保证任何时候 ∑i=1nai<263−1\sum\limits_{i = 1}^{n} a_i < 2^{63} - 1？

      Sol

      发现这个东西和等差数列相似，易于下传标记，考虑用线段树维护。

      发现模数不固定，就不能直接加一个模数的 tag。于是考虑拆开修改的贡献，有一个常用的模数相关的 trick，就是 A mod B=A−⌊AB⌋×BA\bmod B = A - \lfloor\frac{A}{B}\rfloor\times B。思考操作 L,R,A,BL, R, A, B 会对线段树上的 [l,r]∈[L,R][l, r]\in [L, R] 的节点的 sumsum 会产生什么影响：$\sum \limits_{i = L}^{R} A\times (i - L + 1) \bmod B = A\times \frac{(R - L + 1)\times (R - L + 2)}{2} - B\sum\limits_{i = L}^{R} \lfloor\frac{A(i - L + 1)}{B}\rfloor$。前面的部分显然可以直接下传，计算。后面的部分不是很好计算，去掉 BB 换一个形式，并用 lenlen 替代 R−L+1R - L + 1，得到：$\sum \limits_{i = 1}^{len} \lfloor \frac{Ai}{B} \rfloor$。发现这就是一个类欧板子，甚至没有了板子的常数项，会类欧的可以直接跳过下面一段。

      求解 $\sum\limits_{i = 0}^{n} \lfloor\frac{Ai + C}{B}\rfloor$：

      若 A=0A = 0 是简单的，即 (n+1)⌊CB⌋(n + 1)\lfloor \frac{C}{B} \rfloor。

      若 A≤B∧C≤BA\le B \wedge C\le B：令 m=⌊An+CB⌋m = \lfloor \frac{An + C}{B}\rfloor，$\sum\limits_{i = 0}^{n} \lfloor\frac{Ai + C}{B}\rfloor = \sum\limits_{i = 0}^{n} \sum\limits_{j = 1}^{m}[j \le \lfloor \frac{Ai + C}{B} \rfloor]$。其中的中括号是艾弗森括号，其满足条件值为 11，否则为 00。向下取整是很麻烦的，用向下取整的相关性质去掉除号：

      $$\sum\limits_{j = 1}^{m} j\le \lfloor\frac{Ai + C}{B}\rfloor$$$$\Leftrightarrow\sum \limits_{j = 0}^{m - 1} [B(j + 1) \le B\lfloor \frac{Ai + C}{B} \rfloor]$$$$\Leftrightarrow \sum \limits_{j = 0}^{m - 1} [Bj + B - 1 < Ai + C]$$$$\Leftrightarrow \sum \limits_{j = 0}^{m - 1} [\frac{Bj + B - C - 1}{A} < i]$$

      带入得到：$\sum\limits_{i = 0}^{n}\sum \limits_{j = 0}^{m - 1} [\frac{Bj + B - C - 1}{A} < i]$，交换 i,ji, j 维可以得到 $\sum \limits_{j = 0}^{m - 1}\sum\limits_{i = 0}^{n}[\frac{Bj + B - C - 1}{A} < i]$，然后发现后面部分的贡献可以直接计算，于是可以得到 $\sum \limits_{j = 0}^{m - 1}n - \lfloor\frac{Bj + B - C - 1}{A}\rfloor$，在化一下变成 $mn - \sum\limits_{i = 0}^{m - 1}\lfloor \frac{Bi + B - C - 1}{A} \rfloor$。若记 f(A,B,C,n)f(A, B, C, n) 表示 $\sum\limits_{i = 0}^{n} \lfloor\frac{Ai + C}{B}\rfloor$，后面的和式显然就是 f(B,B−C−1,A,m−1)f(B, B - C - 1, A, m - 1)，递归计算即可。

      否则有 $\sum\limits_{i = 0}^{n} \lfloor\frac{Ai + C}{B}\rfloor \Leftrightarrow \sum\limits_{i = 0}^{n} \lfloor\frac{(A\bmod B)i + (C \bmod B)}{B}\rfloor + \frac{n(n + 1)}{2}\lfloor \frac{A}{B}\rfloor + (n + 1) \lfloor \frac{C}{B} \rfloor$，前半部分为 f(A mod B,C mod B,B,n)f(A\bmod B, C\bmod B, B, n) 继续递归即可。

      具体地，在线段树上维护形如 (a,b,t)(a, b, t) 的 tag，表示覆盖的是在当前的 [L,R][L, R] 中，⌊aib⌋\lfloor\frac{ai}{b}\rfloor 的 ii 是从 tt 开始覆盖的，然后线段树进行区间修改和区间求和即可。

      类欧的操作三的复杂度证明参考欧几里得算法，即次数为 O(log⁡n)\mathcal{O}(\log n) 的，而执行第二种操作之后再执行一次 aa 就会变为 00。所以更新线段树上单个节点的复杂度为 O(log⁡n)\mathcal{O}(\log n)，则总时间复杂度为 O(qlog⁡2n)\mathcal{O}(q\log^2 n) 的，空间在离散化后可做到 O(q)\mathcal{O}(q)。

      Code

      #include<bits/stdc++.h>
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define pb emplace_back
#define pii pair < int, int >
#define fi first
#define se second
using namespace std;
int n, m, num;
int b[100010];
struct ques {
	int opt, l, r, a, b;
} q[50010];
ll solve(ll a, ll b, ll c, ll n) {
	if(!a)
		return b / c * (n + 1);
	if(a >= c || b >= c)
		return n * (n + 1) / 2 * (a / c) + (b / c) * (n + 1) + solve(a % c, b % c, c, n);
	ll m = (a * n + b) / c;
	return m * n - solve(c, c - b - 1, a, m - 1);
}
struct Tag {
	ll a, b, t;
	Tag(ll _a = 0, ll _b = 0, ll _t = 0) {
		a = _a, b = _b, t = _t;
	}
}; 
struct segtree {
	Tag laz[400010];
	ll val[400010];
	void tag(int x, ll L, ll R, ll va, ll vb, int t) {
		L = b[L], R = b[R + 1] - 1;
		val[x] = (R - L + 2 + 2 * t) * (R - L + 1) / 2 * va - vb * (solve(va, 0, vb, R - L + 1 + t) - solve(va, 0, vb, t));
		laz[x].a = va, laz[x].b = vb, laz[x].t = t;
	}
	void down(int x, int L, int R) {
		if(laz[x].a && laz[x].b) {
			int mid = (L + R) >> 1;
			tag(x << 1, L, mid, laz[x].a, laz[x].b, laz[x].t);
			tag(x << 1 | 1, mid + 1, R, laz[x].a, laz[x].b, laz[x].t + b[mid + 1] - b[L]);
			laz[x].a = laz[x].b = laz[x].t = 0;
		}
	}
	void modify(int x, int L, int R, int l, int r, ll va, ll vb) {
		if(l <= L && R <= r)
			return tag(x, L, R, va, vb, b[L] - b[l]);
		down(x, L, R);
		int mid = (L + R) >> 1;
		if(l <= mid)
			modify(x << 1, L, mid, l, r, va, vb);
		if(r > mid)
			modify(x << 1 | 1, mid + 1, R, l, r, va, vb);
		val[x] = val[x << 1] + val[x << 1 | 1];
	}
	ll query(int x, int L, int R, int l, int r) {
		if(l <= L && R <= r)
			return val[x];
		down(x, L, R);
		int mid = (L + R) >> 1; ll res = 0;
		if(l <= mid)
			res = query(x << 1, L, mid, l, r);
		if(r > mid)
			res += query(x << 1 | 1, mid + 1, R, l, r);
		return res;
	}
} t;
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	n = 0;
	for(int i = 1; i <= m; ++i) {
		cin >> q[i].opt >> q[i].l >> q[i].r;
		b[++n] = q[i].l;
		b[++n] = ++q[i].r;
		if(q[i].opt == 1)
			cin >> q[i].a >> q[i].b;
	}
	sort(b + 1, b + n + 1);
	n = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= m; ++i) {
		int l = q[i].l, r = q[i].r;
		l = lower_bound(b + 1, b + n + 1, l) - b;
		r = lower_bound(b + 1, b + n + 1, r) - b - 1;
		if(q[i].opt == 1)
			t.modify(1, 1, n - 1, l, r, q[i].a, q[i].b);
		else
			cout << t.query(1, 1, n - 1, l, r) << "\n";
	}
	return 0;
}
      • 1

      [COCI 2009/2010 #1] ALADIN

      信息

      ID
      3603
      时间
      8000ms
      内存
      64MiB
      难度
      9
      标签
      递交数
      47
      已通过
      5
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 26ms
      4. Powered by Hydro v5.0.1 Community