首页 > 其他分享 >【学习笔记】(26) cdq 分治 与 整体二分

【学习笔记】(26) cdq 分治 与 整体二分

时间：2023-09-15 22:13:06浏览次数：51  
标签：二分 26 ch int 分治 mid while cdq getchar

cdq 分治

基本思想

  1. 我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间[L,R]表示。
  2. 分。递归处理左边区间 \([L,M]\) 和右边区间 \([M+1,R]\) 的问题。
  3. 治。合并两个子问题，同时考虑到 \([L,M]\) 内的修改对 \([M+1,R]\) 内的查询产生的影响。即，用左边的子问题帮助解决右边的子问题。

这就是CDQ分治的基本思想。和普通分治不同的地方在于，普通分治在合并两个子问题的过程中，\([L,M]\) 内的问题不会对 \([M+1,R]\) 内的问题产生影响。

应用

1.解决和点对有关的问题

P3810 【模板】三维偏序（陌上花开）

先按照a元素从小到大排序，忽略a元素的影响。然后CDQ分治，按照b元素从小到大的顺序进行归并操作。但是这时候没办法像 求逆序对 一样简单地统计 个数 了，c元素如何处理呢？

这时候比较好的方案就是借助权值树状数组。每次从右边的序列中取出三元组(a,b,c)时，对树状数组查询c值小于(a,b,c)的三元组有多少个；每次从左边序列取出三元组(a,b,c)的时候，根据c值在树状数组中进行修改。注意，每次使用完树状数组记得把树状数组归零。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,k,cnt,nn;
int c[N],ans[N];
struct obj{
	int a,b,c;
	int cnt,id,ans;
}s1[N],s2[N];
bool cmp1(obj x,obj y){
	return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;
}
bool cmp2(obj x,obj y){
	return x.b==y.b?x.c<y.c:x.b<y.b;
}
void add(int x,int delta){
	for(;x<=k;x+=x&-x) c[x]+=delta;
}
int ask(int x){
	int sum=0;
	for(;x;x-=x&-x) sum+=c[x];
	return sum;
}
void cdq(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(s2+l,s2+1+mid,cmp2);
	sort(s2+mid+1,s2+r+1,cmp2);
	int i=mid+1,j=l;
	for(;i<=r;i++){
		while(s2[i].b>=s2[j].b&&j<=mid){
			add(s2[j].c,s2[j].cnt);
			j++;
		}
		s2[i].ans+=ask(s2[i].c);
	}
	for(int i=l;i<j;i++) add(s2[i].c,-s2[i].cnt);
}
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		s1[i].a=read(),s1[i].b=read(),s1[i].c=read();
		s1[i].id=i;
	}
	sort(s1+1,s1+1+n,cmp1);
	for(int i=1;i<=n;i++){
		cnt++;
		if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c){
			s2[++nn].a=s1[i].a,s2[nn].b=s1[i].b,s2[nn].c=s1[i].c,s2[nn].id=s1[i].id,s2[nn].cnt=cnt;
			cnt=0;
		}
	}
	cdq(1,nn);
	for(int i=1;i<=nn;i++) ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
	for(int i=0;i<n;i++) printf("%d\n",ans[i]);
	return 0;
}

2.优化 1D 动态规划转移

1D 动态规划指的是一类特定的 DP 问题，该类题目的特征是 DP 数组是一维的，转移是 O(n) 的。

而分治能把他们的时间复杂度下降到 \(O(nlog^2n)\)

通常，这些 dp 条件是多维偏序。

流程

  1. \(l=r\) 说明 \(dp_r\) 值已经被计算好了，直接令 \(dpr+1\)
  2. 递归使用 \(solve(l,mid)\)
  3. 处理所有 \(l≤j≤mid,mid+1≤i≤r\) 的转移关系
  4. 递归使用 \(solve(mid+1,r)\)

P2487 [SDOI2011] 拦截导弹

朴素dp 是 \(O(n^2)\) 的，因为转移其实是三维偏序（加上时间），考虑用 cdq 来优化。类似三维偏序。

\(f1_i\) 表示以 \(i\) 结尾的最长不降子序列的数量，\(f2_i\) 表示以 \(i\) 开头的最长不降子序列的数量。

\(dp1_i\) 表示以 \(i\) 结尾的最长不降子序列长度，\(dp2_i\) 表示以 \(i\) 开头的最长不降子序列长度。

#include<bits/stdc++.h>
#define db double
#define ll long long
using namespace std;
const int N = 5e4 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}

bool _u;

int n;
struct node{
	int x, y, z;
	ll dp;
	db f;
}a[N];

ll dp1[N], dp2[N], c1[N];
db f1[N], f2[N], c2[N];

bool cmp1(node a, node b){return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y > b.y) : a.x > b.x;}
bool cmp2(node a, node b){return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x;}
bool cmp3(node a, node b){return a.y > b.y;}
bool cmp4(node a, node b){return a.y < b.y;}

void modify(int x, ll dp, db f){
	for(; x <= n; x += x & -x){
		if(c1[x] < dp) c1[x] = dp, c2[x] = f;
		else if(c1[x] == dp) c2[x] += f;
	}
}

ll query1(int x){
	ll res = 0;
	for(; x; x -= x & -x) res = max(res, c1[x]);
	return res;
}

db query2(int x, ll dp){
	db res = 0;
	for(; x; x -= x & -x) if(c1[x] == dp) res += c2[x];
	return res;
}

void del(int x){
	for(; x <= n; x += x & -x) c1[x] = c2[x] = 0;
}

bool check(int i, int j, int opt){
	if(opt == 1) return a[i].y >= a[j].y;
	else return a[i].y <= a[j].y;
}

void merge_sort(int l, int r, int opt){
	int mid = (l + r) >> 1, i = l, j = mid + 1;
	while(i <= mid && j <= r){
		if(check(i, j, opt)) modify(a[i].z, a[i].dp, a[i].f), ++i;
		else{
			int val = query1(a[j].z) + 1;
			if(a[j].dp < val) a[j].dp = val, a[j].f = query2(a[j].z, val - 1);
			else if(a[j].dp == val) a[j].f += query2(a[j].z, val - 1);
			++j;
		}
	}
	while(j <= r){
		int val = query1(a[j].z) + 1;
		if(a[j].dp < val) a[j].dp = val, a[j].f = query2(a[j].z, val - 1);
		else if(a[j].dp == val) a[j].f += query2(a[j].z, val - 1);
		++j;
	}
	for(int _ = l; _ < i; ++_) del(a[_].z);
}

void cdq(int l, int r, int opt){
	if(l == r) return ;
	int mid = (l + r) >> 1;
	cdq(l, mid, opt);
	if(opt == 1) sort(a + l, a + mid + 1, cmp3), sort(a + mid + 1, a + r + 1, cmp3);
	else sort(a + l, a + mid + 1, cmp4), sort(a + mid + 1, a + r + 1, cmp4);
	merge_sort(l, r, opt);
	if(opt == 1) sort(a + mid + 1, a + r + 1, cmp1);
	else sort(a + mid + 1, a + r + 1, cmp2);
	cdq(mid + 1, r, opt);
}

bool _v;

signed main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
//	freopen("3.in", "r", stdin);
//	freopen("1.out", "w", stdout); 
	n = read();
	for(int i = 1; i <= n; ++i){
		a[i].x = read(), a[i].y = read(), a[i].z = i;
		a[i].f = a[i].dp = 1;
	} 
	sort(a + 1, a + 1 + n, cmp1);
	cdq(1, n, 1);
	ll ans = 0;
	for(int i = 1; i <= n; ++i) dp1[a[i].z] = a[i].dp, f1[a[i].z] = a[i].f, ans = max(ans, dp1[a[i].z]);
	printf("%lld\n", ans);
	for(int i = 1; i <= n; ++i) a[i].z = n - a[i].z + 1, a[i].dp = a[i].f = 1;
	sort(a + 1, a + 1 + n, cmp2);
	cdq(1, n, 2);
	db k = 0;
	for(int i = 1; i <= n; ++i){
		dp2[n - a[i].z + 1] = a[i].dp, f2[n - a[i].z + 1] = a[i].f;
		if(dp2[n - a[i].z + 1] == ans) k += f2[n - a[i].z + 1];
	} 
	for(int i = 1; i <= n; ++i){
		if(dp1[i] + dp2[i] == ans + 1) printf("%.5lf", f1[i] * f2[i] / k);
		else printf("0.00000");
		if(i < n) printf(" ");
	}
	puts("");
	return 0;
}

3.动态问题转化为静态问题

前两种情况使用分治目的是： 将序列折半，递归处理点对间的关系。

不过现在要求折半 时间序列。

它适用于一些「需要支持做 XXX 修改然后做 XXX 询问」的数据结构题。该类题目有两个特点：

  1. 把询问离线，所有操作会按时间排成一个序列。
  2. 每一个修改和之后的询问息相关，有 \(O(n^2)\) 对。

分治的操作和处理点对关系的分支操作也相同。

如果各个修改之间是 独立 的话，就不需要处理左右区间的时序问题。

如果不独立，那么两个区间可能会进行依赖关系，此时所有跨越 \(mid\) 的修改必须放在 \(solve(l,mid)\) 和 \(solve(mid+1,r)\) 之间。

P3206 [HNOI2010] 城市建设

我们可以通过分治，一层层的统一求出一定用到的边和一定用不到的边，达到减少边数的效果，最后到达边界时再进行暴力，可以起到很好的加速效果。本质上就是将单独选边转化为给一个区间的所有询问选边，起到优化时间的效果。

具体的，我们的函数 CDQ(l, r) 就是要删除对于 \(l,r\) 中的讯问，能够确定一定选或者一定不选的边。

具体的，我们把 [l,r] 中要修改的边的权值都改为 \(-\infty\)，再与当前边集 f 中的边跑一次最小生成树，把 f 中的边两边端点直接进行缩点（合并）。由于 fff 中的边一定能形成一棵生成树（因为原图存在生成树，并且每次分治的时候，该计算过程只删了一定不选的边，而一定选的边也进行了缩点，所以必定存在生成树），所以最多只是那 \(r - l + 1\) 个修改的边的端点没有连到一起，所以点的个数为 \(O(r - l + 1)\)。

然后，我们再把 \([l,r]\) 中要修改的边的权值都改为 \(+\infty\)，再与当前边集 f 中的边跑一次最小生成树（f 已经经过缩点）。没有选上的边就是无用的边，边的个数与点同阶，为 \(O(r−l+1)\)。

而计算顺序是：先按顺序执行上述计算，再计算 CDQ(l,mid)，再计算 CDQ(mid+1,r)。只有这样才能保证计算 CDQ(l,r) 时， 1 到 l−1 的所有边权都修改了过来。而上述两步计算出来的边是在不管 [l,r] 怎么修改边权都成立的，所以没有关系。最后，我们带着计算出来的边，进行下一层递归即可。

#include<bits/stdc++.h>
#define db double
#define ll long long
#define INF 1e9
using namespace std;
const int N = 5e4 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}

bool _u;

int n, m, q;
int a[N], b[N], c[N], fa[N], ct[N];
ll ans[N];
struct edge{
	int u, v, w, id;
	bool operator < (const edge &A) const{return w < A.w;}
}e[20][N], f[N], g[N];

int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}

void clear(int tot){
	for(int i = 1; i <= tot; ++i) fa[f[i].u] = f[i].u, fa[f[i].v] = f[i].v;
}

void cdq(int l, int r, int now, int tot, ll sum){
	if(l == r) ct[a[l]] = b[l];
	for(int i = 1; i <= tot; ++i) e[now][i].w = ct[e[now][i].id], c[e[now][i].id] = i, f[i] = e[now][i];
	clear(tot);
	if(l == r){
		ans[l] = sum, sort(f + 1, f + 1 + tot);
		for(int i = 1; i <= tot; ++i){
			int x = find(f[i].u), y = find(f[i].v);
			if(x == y) continue;
			ans[l] += f[i].w, fa[x] = y;
		}
		return ;
	}
	for(int i = l; i <= r; ++i) f[c[a[i]]].w = -INF;
	sort(f + 1, f + 1 + tot);
	int cnt = 0;
	for(int i = 1; i <= tot; ++i){
		int x = find(f[i].u), y = find(f[i].v);
		if(x == y) continue; fa[x] = y;
		if(f[i].w != -INF) g[++cnt] = f[i], sum += f[i].w;
	}
	clear(tot);
	for(int i = 1; i <= cnt; ++i) fa[find(g[i].u)] = g[i].v;
	cnt = 0;
	for(int i = 1; i <= tot; ++i){
		int x = find(f[i].u), y = find(f[i].v);
		if(x == y) continue;
		f[++cnt].u = x, f[cnt].v = y, f[cnt].w = f[i].w, f[cnt].id = f[i].id;
	}
	tot = cnt;
	for(int i = 1; i <= tot; ++i) c[f[i].id] = i;
	for(int i = l; i <= r; ++i) f[c[a[i]]].w = INF;
	clear(tot);
	sort(f + 1, f + 1 + tot);
	cnt = 0;
	for(int i = 1; i <= tot; ++i){
		if(f[i].w == INF){f[++cnt] = f[i]; continue;}
		int x = find(f[i].u), y = find(f[i].v);
		if(x == y) continue;
		fa[x] = y, f[++cnt] = f[i];
	}
	tot = cnt;
	for(int i = 1; i <= tot; ++i) e[now + 1][i] = f[i];
	int mid = (l + r) >> 1;
	cdq(l, mid, now + 1, tot, sum);
	cdq(mid + 1, r, now + 1, tot, sum);
}

bool _v;

signed main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	

	n = read(), m = read(), q = read();
	for(int i = 1; i <= m; ++i) e[0][i].u = read(), e[0][i].v = read(), e[0][i].w = read(), e[0][i].id = i, ct[i] = e[0][i].w;
	for(int i = 1; i <= q; ++i) a[i] = read(), b[i] = read();
	cdq(1, q, 0, m, 0);
	for(int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
	return 0;
}

整体二分

整体二分主要是把所有查询放在一起二分答案, 然后把操作也一起分治.

对没错, 放在一起. 计算的时候扫一遍当前处理的区间, 把答案在 [l,mid] 的查询放在一边递归下去, (mid,r] 的放在另一边递归下去, 递归到叶子就有答案了.

其实有点像是二分在数据结构题目上的扩展, 因为数据结构题一般不仅有多组查询还有其他的修改...

什么时候可以使用呢？

  1. 询问的答案具有可二分性。
  2. 修改对判定答案的贡献互相独立,修改之间互不影响效果。
  3. 修改如果对判定答案有贡献,则贡献为确定的判定标准无关的值。
  4. 贡献满足交换律,结合律,具有可加性。

记 [l,r] 为答案的值域，[L,R] 为答案的定义域(下标在 [L,R]之间)

  1. 首先把所有操作按照时间顺序存入数组中，然后开始分治。
  2. 在每一层分治中，利用数据结构统计当前查询的答案和 mid之间的关系（感觉有点像 CDQ分治）
  3. 根据查询出来的答案和 mid之间的关系，将当前处理的操作序列分成 \(q_1\) 和 \(q_2\) 两份，并且递归。
  4. 当 l=r，记录答案返回即可。

带修区间第 k 小

P2617 Dynamic Rankings

为了方便，将询问和修改统称为操作。因为后面的操作会依赖于前面的操作，因此可以将所有操作存在一个数组里，使用 标记 区分类型。

修改操作可以理解成：从原数列中删除一个数再添加一个数。

因此，可转化为：树状数组中删除之前的数，再插入现在的数。

数列的初始化操作可简化为插入操作。

首先原序列记为 \(A\) 。对于答案区间为 ，有以下操作：

1、将A序列中值在 \([l,mid]\) 的在序列中的位置单点修改（树状数组）

2、对于每一个询问 \(p\)

在树状数组中查询 \(l-1\) 和 \(r\) 的前缀和，插值就是这个区间内小于等于 \(mid\) 的个数 \(cnt\) 。

如果当前询问 \(k \le cnt\)，那就把这个询问归到 \([l, mid]\) 的小问题中；如果 \(k > cnt\)，就让 \(k = k - cnt\)，然后把它分到 \([mid + 1, r]\) 这个小问题中（类似于CDQ的过程）

3、清空树状数组，递归到 \([l, mid], [mid + 1, r]\) 中

当 \(l== r\)，答案就是 \(l\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 57, INF = 1e9; 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f; 
}

bool _u;

int n, m, cnt;
int a[N], ans[N], c[N];
struct node{
	int x, y, k, id, opt;
}q[N], q1[N], q2[N];

void add(int x, int k){
	for(; x <= n; x += x & -x) c[x] += k;
}

int ask(int x){
	int res = 0;
	for(; x; x -= x & -x) res += c[x];
	return res;
}

void solve(int L, int R, int l, int r){
	if(l > r || L > R) return ;
	if(l == r){
		for(int i = L; i <= R; ++i) if(q[i].opt == 2) ans[q[i].id] = l;
		return ;
	}
	int cnt1 = 0, cnt2 = 0, mid = (l + r) >> 1;
	for(int i = L; i <= R; ++i){
		if(q[i].opt != 2){
			if(q[i].x <= mid) add(q[i].id, q[i].opt), q1[++cnt1] = q[i]; //只需要考虑左边对右边的贡献 
			else q2[++cnt2] = q[i];
		}else{
			int res = ask(q[i].y) - ask(q[i].x - 1);  
			if(res >= q[i].k) q1[++cnt1] = q[i];   
			else q[i].k -= res, q2[++cnt2] = q[i];
		}
	}
	for(int i = 1; i <= cnt1; ++i) if(q1[i].opt != 2) add(q1[i].id, -q1[i].opt);
	for(int i = 1; i <= cnt1; ++i) q[i + L - 1] = q1[i];
	for(int i = 1; i <= cnt2; ++i) q[i + L + cnt1 - 1] = q2[i];
	solve(L, L + cnt1 - 1, l, mid), solve(L + cnt1, R, mid + 1, r);
}

bool _v;

int main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) a[i] = read(), q[++cnt] = {a[i], 0, 0, i, 1};
	int num = 0;
	for(int i = 1; i <= m; ++i){
		char ch[5]; scanf("%s", ch + 1); 
		int l, r, x, k;
		if(ch[1] == 'Q'){
			l = read(), r = read(), k = read();
			q[++cnt] = {l, r, k, ++num, 2};
		}else{
			x = read(), k = read();
			q[++cnt] = {a[x], 0, 0, x, -1}, q[++cnt] = {a[x] = k, 0, 0, x, 1};
		}
	}
	solve(1, cnt, 0, INF);
	for(int i = 1; i <= num; ++i) printf("%d\n", ans[i]);
	return 0;
}

P4602 [CTSC2018] 混合果汁

整体二分，将美味度不小于 \(mid\) 的果汁都拎出来，询问最小价钱，分成 \(q1\) 和 \(q2\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 57, INF = 1e18; 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f; 
}

bool _u;

int n, m, sum;
int ans[N], c[N], s[N];
struct node{
	int d, p, l;
	bool operator < (const node &A) const{return d > A.d;}
}a[N];

struct query{
	int g, L, id;
}b[N], q1[N], q2[N];

void add(int x, int k){
	int w = x * k; sum += k;
	for(; x < N; x += x & -x) c[x] += k, s[x] += w;
}

int ask(int k){
	if(k > sum) return INF;
	int x = 0, res = 0;
	for(int i = 16; ~i; --i){
		int nx = x + (1 << i);
		if(nx >= N || c[nx] >= k) continue;
		k -= c[nx]; res += s[nx]; x = nx;
	}
	return res + (x + 1) * k;
}

void solve(int l, int r, int L, int R){
	if(l > r || L > R) return ;
	if(l == r){
		if(l > n) return ;
		for(int i = L; i <= R; ++i) ans[b[i].id] = a[l].d;
		return ;
	}
	int mid = (l + r) >> 1;
	for(int i = l; i <= mid; ++i) add(a[i].p, a[i].l);
	int cnt1 = 0, cnt2 = 0;
	for(int i = L; i <= R; ++i){
		int x = ask(b[i].L);
		if(x <= b[i].g) q1[++cnt1] = b[i];
		else q2[++cnt2] = b[i]; 
	}
	for(int i = 1; i <= cnt1; ++i) b[i + L - 1] = q1[i];
	for(int i = 1; i <= cnt2; ++i) b[i + L + cnt1 - 1] = q2[i];
	solve(mid + 1, r, L + cnt1, R);
	for(int i = l; i <= mid; ++i) add(a[i].p, -a[i].l);
	solve(l, mid, L, L + cnt1 - 1);
}

bool _v;

signed main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) a[i].d = read(), a[i].p = read(), a[i].l = read();
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= m; ++i) b[i].g = read(), b[i].L = read(), b[i].id = i;
	memset(ans, -1, sizeof(ans));
	solve(1, n + 1, 1, m);
	for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
	return 0;
}

P3527 [POI2011] MET-Meteors

整体二分，就是因为是环，所以有些点要特殊处理。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e5 + 67; 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f; 
}

bool _u;

int n, m, k;
int p[N], ans[N], c[N];
vector<int> own[N];
struct qry{
	int l, r, a, opt, id;
}q[N], q1[N], q2[N];

void add(int x, int k){
	if(!x) return ;
	for(; x <= m; x += x & -x) c[x] += k;
}

int ask(int x){
	int res = 0;
	for(; x; x -= x & -x) res += c[x];
	return res;
}

void solve(int L, int R, int l, int r){
	if(L > R || l > r) return ;
	if(l == r){
		for(int i = L; i <= R; ++i)
			if(q[i].opt == 2) ans[q[i].id] = l;
		return ;
	}
	int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
	for(int i = L; i <= R; ++i){
		if(q[i].opt == 2){
			int res = 0;
			for(auto j : own[q[i].id]){
				res += ask(j);
				if(res >= q[i].a) break;
			} 
			if(q[i].a <= res) q1[++cnt1] = q[i];
			else q[i].a -= res, q2[++cnt2] = q[i]; 
		}else{
			if(q[i].id <= mid){
				if(q[i].opt == 1) add(1, q[i].a), add(q[i].r + 1, -q[i].a), add(q[i].l, q[i].a);
				else add(q[i].l, q[i].a), add(q[i].r + 1, -q[i].a);
				q1[++cnt1] = q[i];
			}else q2[++cnt2] = q[i];
		}
	}
	for(int i = L; i <= R; ++i){
		if(q[i].opt != 2 && q[i].id <= mid){
			if(q[i].opt == 1) add(1, -q[i].a), add(q[i].r + 1, q[i].a), add(q[i].l, -q[i].a);
			else add(q[i].l, -q[i].a), add(q[i].r + 1, q[i].a);
		}
	}
	for(int i = 1; i <= cnt1; ++i) q[i + L - 1]= q1[i];
	for(int i = 1; i <= cnt2; ++i) q[i + L + cnt1 - 1] = q2[i];
	solve(L, L + cnt1 - 1, l, mid);
	solve(L + cnt1, R, mid + 1, r);
}

bool _v;

signed main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
	n = read(), m = read();
	for(int i = 1, x; i <= m; ++i) x = read(), own[x].push_back(i);
	for(int i = 1; i <= n; ++i) p[i] = read();
	k = read();
	for(int i = 1; i <= k; ++i){
		q[i].l = read(), q[i].r = read(), q[i].a = read(), q[i].id = i;
		if(q[i].r < q[i].l) q[i].opt = 1; 
	}
	for(int i = 1; i <= n; ++i) q[i + k].a = p[i], q[i + k].opt = 2, q[i + k].id = i;
	solve(1, k + n, 1, k + 1);
	for(int i = 1; i <= n; ++i){
		if(ans[i] != k + 1) printf("%d\n", ans[i]);
		else printf("NIE\n");
	}
 	return 0;
}

P1527 [国家集训队] 矩阵乘法

维护改为二维树状数组维护前缀和即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e2 + 57, M = 6e5 + 67; 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f; 
}

bool _u;

int n, m, cnt, minn = 1e9, maxn;
struct qry{
	int a1, b1, a2, b2, k, id;
}q[M], q1[M], q2[M];
int c[N][N], ans[M];

void add(int x, int y, int v){
	for(int i = x; i <= n; i += i & -i)
		for(int j = y; j <= n; j += j & -j)
			c[i][j] += v;
} 

int ask(int x, int y){
	int res = 0;
	for(int i = x; i; i -= i & -i)
		for(int j = y; j; j -= j & -j)
			res += c[i][j];
	return res;
}

void solve(int l, int r, int L, int R){
	if(l > r || L > R) return ;
	if(l == r){
		for(int i = L; i <= R; ++i) ans[q[i].id] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	int cnt1 = 0, cnt2 = 0;
	for(int i = L; i <= R; ++i){
		if(q[i].id == 0) {
			if(q[i].k <= mid) add(q[i].a1, q[i].b1, 1), q1[++cnt1] = q[i];
			else q2[++cnt2] = q[i];
		}else{
			int tmp = ask(q[i].a2, q[i].b2) - ask(q[i].a1 - 1, q[i].b2) - ask(q[i].a2, q[i].b1 - 1) + ask(q[i].a1 - 1, q[i].b1 - 1);
			if(tmp >= q[i].k) q1[++cnt1] = q[i];
			else q[i].k -= tmp, q2[++cnt2] = q[i];
		}
	}
	for(int i = 1; i <= cnt1; ++i) q[L + i - 1] = q1[i];
	for(int i = 1; i <= cnt2; ++i) q[L + cnt1 + i - 1] = q2[i];
	for(int i = 1; i <= cnt1; ++i) if(!q1[i].id && q1[i].k <= mid) add(q1[i].a1, q1[i].b1, -1);
	solve(l, mid, L, L + cnt1 - 1);
	solve(mid + 1, r, L + cnt1, R);
}

bool _v;

signed main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
	
	n = read(), m = read();
	for(int i = 1, x; i <= n; ++i)
		for(int j = 1; j <= n; ++j) q[++cnt] = {i, j, 0, 0, x = read(), 0}, minn = min(minn, x), maxn = max(maxn, x);
	for(int i = 1, a1, a2, b1, b2, k; i <= m; ++i)
		q[++cnt] = {a1 = read(), b1 = read(), a2 = read(), b2 = read(), k = read(), i};
	solve(0, 1e9, 1, cnt);
	for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
 	return 0;
}

参考: https://www.cnblogs.com/guanlexiangfan/p/15473204.html

标签：二分,26,ch,int,分治,mid,while,cdq,getchar
From： https://www.cnblogs.com/jiangchen4122/p/17694555.html

相关文章

  • Si3262| 三合一低功耗MCU+NFC+防水的触摸按键SOC芯片
    Si3262是一款高度集成的低功耗SOC芯片，其集成了基于RISC-V核的低功耗MCU和工作在13.56MHz的非接触式读写器模块。MCU模块具有低功耗、LowPinCount、宽电压工作范围，集成了13/14/15/16位精度的ADC、LVD、UART、SPI、I2C、TIMER、WUP、IWDG、RTC、TSC等丰富的外设。内......
  • 20211326德永学习笔记2
    第九章总结要点1.I/O库函数与系统调用系统调用函数：open()、read()、write()、lseek()、close()；I/O库函数：fopen()、fread()、fwrite()、flseek()、fclose()。I/O库函数一一对应地依赖于系统调用函数。2、I/O库函数的算法-2.1fread算法在第一次调用fread()时，FILE结构体的缓......
  • HDU 1054 Strategic Game 树形DP/二分图匹配
    第一次写博文，想了半天就拿一道dp/graph的题作为处作吧此题有两种常见解法（题意比较简单，就不赘述）1.二分图最大匹配       此题等价于问一棵树中最小点覆盖数。树形结构可以把它看做是一个二分图，一个点集为奇数层，另一个点集为偶数层，显然满足二分图定义，可以套用求二分图最小点......
  • 2023.9.14 整数二分排序
    1#二分23##整数二分45~~~c++6//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用7inttest01(intl,intr)8{9while(l<r)10{11intmid=(l+r)/2;12boolcheck(intmid);//check判断mid是否满足x性质13if(check(......
  • ubuntu编译ffmpeg扩展支持FLV-H265
    1.编译x264：  1）gitclonehttp://git.videolan.org/git/x264.git  2）./configure--enable-shared--disable-asm  3）make&&makeinstall2.编译x265：  1）wgethttp://ftp.videolan.org/pub/videolan/x265/x265-2.7.tar.bz2  2）tarxvfx265-2.7.tar.b......
  • 算法回顾之三：二分查找
    算法回顾系列第三篇：二分查找算法------------------------------------------------二分查找算法 基本原理：首先,假设表中元素是按升序排列.将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功.否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键......
  • windows defender怎么关闭https://www.lingfenmao.com/it/2643.html
    工具/原料：       品牌型号：联想昭阳K4e-IML       系统版本：Windows10        关闭windowsdefender放火墙可使用组策略禁用和安全中心两种方法操作，以下为组策略禁用关闭的步骤说明：方法一：组策略禁用法1打开电脑Win+R键打开命令框......
  • 用c++ 实现 二分查找 前提是先把数组排列好
    #include<iostream>usingnamespacestd;//可以递归调用的二分查找intsearch(constint(&a)[10],intstart,intend,inttarget){ //基准情况：目标值超出范围，或者start>end，说明没有找到 if(target<a[start]||target>a[end]||start>end) return-1; //取二分......
  • macOS Monterey 12.6.9 (21G726) 正式版发布，ISO、IPSW、PKG 下载
    macOSMonterey12.6.9(21G726)正式版发布，ISO、IPSW、PKG下载本站下载的macOS软件包，既可以拖拽到Applications（应用程序）下直接安装，也可以制作启动U盘安装，或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。2023年9月12日，Apple为macOS和......
  • macOS Monterey 12.6.9 (21G726) Boot ISO 原版可引导镜像
    macOSMonterey12.6.9(21G726)BootISO原版可引导镜像本站下载的macOS软件包，既可以拖拽到Applications（应用程序）下直接安装，也可以制作启动U盘安装，或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。2023年9月12日，Apple为macOS和iOS等......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99