2023NOIP A层联测9 风信子

2023-10-14 18:04
文章标签 联测 2023noip 风信子

本文主要是介绍2023NOIP A层联测9 风信子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意

有一个长度为 n n n的序列 a a a

定义一个合法的二元组 ( i , j ) (i,j) (i,j)满足 i , j i,j i,j为整数且 i ≤ j i\leq j ij,合法二元组的分数为 a i − a j a_i-a_j aiaj。定义一个合法二元组 ( i , j ) (i,j) (i,j)在区间 [ l , r ] [l,r] [l,r]内,当且仅当 l ≤ i , j ≤ r l\leq i,j\leq r li,jr

m m m次操作,每次操作有两个类型:

  • 1 l r x:表示将 a a a中第 l l l个位置到第 r r r个位置加 x x x
  • 2 l r k:表示询问选出 k k k个在区间 [ l , r ] [l,r] [l,r]内不同的二元组 ( i , j ) (i,j) (i,j)的最大分数和是多少

1 ≤ n , m ≤ 1 0 5 , − 1 0 6 ≤ a i , x ≤ 1 0 6 , ∑ k ≤ 3 × 1 0 5 1\leq n,m\leq 10^5,-10^6\leq a_i,x\leq 10^6,\sum k\leq 3\times 10^5 1n,m105,106ai,x106,k3×105

数据保证 [ l , r ] [l,r] [l,r]中至少有 k k k个合法二元组。


题解

我们先考虑 k = 1 k=1 k=1的情况。也就是说,要在区间 [ l , r ] [l,r] [l,r]中找到一个合法二元组 ( i , j ) (i,j) (i,j)使得 a i − a j a_i-a_j aiaj最大。

可以用线段树解决。线段树维护三个值:区间最大值 m x mx mx,区间最小值 m n mn mn,区间最大答案 a n s ans ans

那么,对于一个点 p p p a n s p = max ⁡ ( a n s l s , a n s r s , m x l s − m n r s ) ans_p=\max(ans_{ls},ans_{rs},mx_{ls}-mn_{rs}) ansp=max(ansls,ansrs,mxlsmnrs)

当整体加上某个值的时候,若一个区间内都需要加,则最大值 m x mx mx和最小值 m n mn mn增加,但因为答案是两个 a a a的差,所以最大答案 a n s ans ans不变。

这样,我们就解决了 k = 1 k=1 k=1的情况。。

我们可以用一个结构体来表示 i ∈ [ l 1 , r 1 ] i\in[l_1,r_1] i[l1,r1] j ∈ [ l 2 , r 2 ] j\in[l_2,r_2] j[l2,r2]并存储其最优的一组合法二元组 ( i , j ) (i,j) (i,j)以及其分数,我们可以把这些 ( i , j ) (i,j) (i,j)看成一个矩形。每次处理完一个矩形,就将这个矩形分成不包括最优合法二元组多个矩形继续来求,此时能保证原矩形分成的多个矩形中每个矩形的最优合法二元组的分数都不超过原矩形的分数。可以用优先队列,按最优合法二元组的分数从大到小排序,选了 k k k个最优合法二元组并计算贡献之后就不需要再选了。

一般的矩形是不好求解答案的,不过有两种矩形可以:

  • 左右端点所属区间完全重合,此时用上面 k = 1 k=1 k=1的做法即可得到答案
  • 左右端点所属区间没有交集,此时求左边的最大值和右边的最小值,作差即可得到答案

显然题意要询问的就是第一种矩形。

那能不能在每次分裂的时候都将矩形分裂为这两种矩形呢?是可以的。

对于第一种矩形, i , j ∈ [ l , r ] i,j\in[l,r] i,j[l,r],假设最优解位于 ( x , y ) (x,y) (x,y),我们可以将这个矩形分为如下几种矩形:

  • i ∈ [ l , x − 1 ] , j ∈ [ l , x − 1 ] i\in[l,x-1],j\in[l,x-1] i[l,x1],j[l,x1],需满足 x > l x>l x>l
  • i ∈ [ l , x − 1 ] , j ∈ [ x , r ] i\in[l,x-1],j\in[x,r] i[l,x1],j[x,r],需满足 x > l x>l x>l
  • i ∈ [ x , x ] , j ∈ [ x , x ] i\in[x,x],j\in[x,x] i[x,x],j[x,x],需满足 x ≠ y x\neq y x=y
  • i ∈ [ x , x ] , j ∈ [ x + 1 , y − 1 ] i\in[x,x],j\in[x+1,y-1] i[x,x],j[x+1,y1],需满足 x < y − 1 x<y-1 x<y1
  • i ∈ [ x , x ] , j ∈ [ y + 1 , r ] i\in[x,x],j\in[y+1,r] i[x,x],j[y+1,r],需满足 y < r y<r y<r
  • i ∈ [ x + 1 , r ] , j ∈ [ x + 1 , r ] i\in[x+1,r],j\in[x+1,r] i[x+1,r],j[x+1,r],需满足 x < r x<r x<r

对于第二种矩形, i ∈ [ l 1 , r 1 ] , j ∈ [ l 2 , r 2 ] i\in[l_1,r_1],j\in[l_2,r_2] i[l1,r1],j[l2,r2],假设最优解位于 ( x , y ) (x,y) (x,y),我们可以将这个矩形分为如下几种矩形:

  • i ∈ [ l 1 , x − 1 ] , j ∈ [ l 2 , r 2 ] i\in[l_1,x-1],j\in[l_2,r_2] i[l1,x1],j[l2,r2],需满足 x > l 1 x>l_1 x>l1
  • i ∈ [ x , x ] , j ∈ [ l 2 , y − 1 ] i\in[x,x],j\in[l_2,y-1] i[x,x],j[l2,y1],需满足 l 2 < y l_2<y l2<y
  • i ∈ [ x , x ] , j ∈ [ y + 1 , r 2 ] i\in[x,x],j\in[y+1,r_2] i[x,x],j[y+1,r2],需满足 y < r 2 y<r_2 y<r2
  • i ∈ [ x + 1 , r 1 ] , j ∈ [ l 2 , r 2 ] i\in[x+1,r_1],j\in[l_2,r_2] i[x+1,r1],j[l2,r2],需满足 x < r 1 x<r_1 x<r1

这样,问题就解决了。

时间复杂度为 O ( n log ⁡ n + ( ∑ k ) ( log ⁡ n + log ⁡ ( ∑ k ) ) ) O(n\log n+(\sum k)(\log n+\log(\sum k))) O(nlogn+(k)(logn+log(k)))

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=100000;
int n,m,mxl,wl,wr,mxw[4*N+5],mnw[4*N+5],cl[4*N+5],cr[4*N+5];
long long ans,mxd,zl,zr,a[N+5],mx[4*N+5],mn[4*N+5],tr[4*N+5],ly[4*N+5];
struct node{int l1,r1,l2,r2,z,x,y;long long vl;bool operator<(const node ax)const{return vl<ax.vl;}
};
priority_queue<node>q;
void up(int k){if(mx[lc]>mx[rc]) mx[k]=mx[lc],mxw[k]=mxw[lc];else mx[k]=mx[rc],mxw[k]=mxw[rc];if(mn[lc]<mn[rc]) mn[k]=mn[lc],mnw[k]=mnw[lc];else mn[k]=mn[rc],mnw[k]=mnw[rc];tr[k]=max(max(tr[lc],tr[rc]),mx[lc]-mn[rc]);if(tr[k]==tr[lc]) cl[k]=cl[lc],cr[k]=cr[lc];else if(tr[k]==tr[rc]) cl[k]=cl[rc],cr[k]=cr[rc];else cl[k]=mxw[lc],cr[k]=mnw[rc];
}
void build(int k,int l,int r){if(l==r){mx[k]=mn[k]=a[l];mxw[k]=mnw[k]=cl[k]=cr[k]=l;tr[k]=0;return;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);up(k);
}
void down(int k){mx[lc]+=ly[k];mn[lc]+=ly[k];ly[lc]+=ly[k];mx[rc]+=ly[k];mn[rc]+=ly[k];ly[rc]+=ly[k];ly[k]=0;
}
void ch(int k,int l,int r,int x,int y,int v){if(l>=x&&r<=y){mx[k]+=v;mn[k]+=v;ly[k]+=v;return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y,v);if(y>mid) ch(rc,mid+1,r,x,y,v);up(k);
}
void find(int k,int l,int r,int x,int y){if(l>=x&&r<=y){ans=max(max(ans,tr[k]),mxd-mn[k]);if(ans==tr[k]) wl=cl[k],wr=cr[k];else if(ans==mxd-mn[k]) wl=mxl,wr=mnw[k];if(mx[k]>mxd) mxd=mx[k],mxl=mxw[k];return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) find(lc,l,mid,x,y);if(y>mid) find(rc,mid+1,r,x,y);
}
void gtmx(int k,int l,int r,int x,int y){if(l>=x&&r<=y){if(zl<mx[k]) zl=mx[k],wl=mxw[k];return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) gtmx(lc,l,mid,x,y);if(y>mid) gtmx(rc,mid+1,r,x,y);
}
void gtmn(int k,int l,int r,int x,int y){if(l>=x&&r<=y){if(zr>mn[k]) zr=mn[k],wr=mnw[k];return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) gtmn(lc,l,mid,x,y);if(y>mid) gtmn(rc,mid+1,r,x,y);
}
void pls(int l1,int r1,int l2,int r2,int z){if(z==1){ans=mxd=-1e18;find(1,1,n,l1,r1);q.push((node){l1,r1,l2,r2,z,wl,wr,ans});}else{zl=-1e18;zr=1e18;gtmx(1,1,n,l1,r1);gtmn(1,1,n,l2,r2);q.push((node){l1,r1,l2,r2,z,wl,wr,zl-zr});}
}
void work(int vl,int vr,int x){pls(vl,vr,vl,vr,1);long long sum=0;for(int o=1;o<=x;o++){node t=q.top();q.pop();sum+=t.vl;int x=t.x,y=t.y;if(t.z==1){int l=t.l1,r=t.r1;if(x>l) pls(l,x-1,l,x-1,1);if(x>l) pls(l,x-1,x,r,2);if(x!=y) pls(x,x,x,x,1);if(x<y-1) pls(x,x,x+1,y-1,2);if(y<r) pls(x,x,y+1,r,2);if(x<r) pls(x+1,r,x+1,r,1);}else{if(x>t.l1) pls(t.l1,x-1,t.l2,t.r2,2);if(t.l2<y) pls(x,x,t.l2,y-1,2);if(y<t.r2) pls(x,x,y+1,t.r2,2);if(x<t.r1) pls(x+1,t.r1,t.l2,t.r2,2);}}printf("%lld\n",sum);while(!q.empty()) q.pop();
}
int main()
{freopen("D.in","r",stdin);freopen("D.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}build(1,1,n);for(int o=1,tp,l,r,x;o<=m;o++){scanf("%d%d%d%d",&tp,&l,&r,&x);if(tp==1) ch(1,1,n,l,r,x);else work(l,r,x);}return 0;
}

这篇关于2023NOIP A层联测9 风信子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/212219

相关文章

NOIP2023模拟16联测37 大眼鸹猫

题目大意 有两个长度为 n n n的序列 a , b a,b a,b,这两个序列都是单调不降的。 你可以对 a a a进行不超过 m m m次操作,每次操作你可以选择一个 i i i满足 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n,然后选择一个整数(可以是负数) x x x,将 a i a_i ai​加上 x x x,这次操作要花费 x 2 x^2 x2的代价。 在操作的过程

NOIP2023模拟16联测37 总结

NOIP2023模拟16联测37 总结 T 1 T1 T1 求有多少区间的异或和为 k k k 的因子, n , k ≤ 1 0 5 n , k \le 10^5 n,k≤105 。看到异或就想到了前几天的拿到按位考虑的题目,想了半小时没想到。突然想前缀和,对每个 k k k 的因子记录一下 a ⊕ k a \oplus k a⊕k 的数量就好了 。 T 2 T2 T2 每次可以删去

NOIP2023模拟16联测37 D. 小猫吃火龙果

NOIP2023模拟16联测37 D. 小猫吃火龙果 文章目录 NOIP2023模拟16联测37 D. 小猫吃火龙果题目大意思路code 题目大意 有 n n n 个物品 A A A , B B B , C C C , A A A 吃 B B B, B B B 吃 C C C, C C C 吃 A A A,有两种操作,给 [ l , r ] [ l , r ]

2023.11.10联测总结

T 1 T1 T1求的是有多少个区间的异或和是 k k k的因子, n , k ≤ 1 0 5 n,k \leq 10^5 n,k≤105。 这道题用前缀和维护一下,暴力枚举所有区间就有 80 80 80分。 有一瞬间想过枚举因数,但是脑抽以为要 O ( n ) \mathcal O(n) O(n)枚举,然后就跑路了。 T 2 T_2 T2​给出一个有 n n n个数的数列,每次可以删去

2023NOIP A层联测28-大眼鸹猫

给你两个长度为 n n n 的序列 a , b a,b a,b,这两个序列都是单调不降的。 你可以对 a a a 进行不超过 m m m 次操作,每次操作你可以选择一个 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n,然后选择一个整数(可以是负数) x x x,将 a i a_i ai​ 加上 x x x,这一次操作需要花费 x 2 x^2 x2 的代

NOIP2023模拟13联测34 B.competition

NOIP2023模拟13联测34 B.competition 文章目录 NOIP2023模拟13联测34 B.competition题目大意思路code 题目大意 现在有 n n n 个区间 [ l i , r i ] [l_i , r_i] [li​,ri​] ,现在问你选取若干的连续的区间的区间并的大小的和。 思路 设 p r e i , j pre_{i ,

NOIP2023模拟1联测22 爆炸

NOIP2023模拟1联测22 爆炸 题目大意 ​ 自己看 思路 当一个炸弹被引爆后,它的方向是固定的。如果被竖着引爆,那么应该选择横着引爆,否则选择竖着引爆,这是显然 的。 考虑对于每个炸弹 ( i , j ) (i , j) (i,j) 将第 i i i 行和第 j j j 列连边 对于每个水晶 ( i , j ) (i , j) (i,j) 如果 i i i 行和

NOIP2023模拟13联测34 competition

题目大意 有一场题目数量为 m m m的比赛,有一个团队想要来参加。 这个团队有 n n n个选手,编号为 i i i的选手能做第 l i ∼ r i l_i \sim r_i li​∼ri​道题,每题他都有 100 % 100\% 100%的概率做出来。 这个团队会随机派出一只队伍来参加这个比赛。 因为编号相邻的人关系更好,默契度也更高,所以一个团队派出的队伍一直都是编号为连续区间的选手

2023NOIP A层联测26-origen

给定 n n n 个整数 a 1 , a 2 … a n a_1,a_2\dots a_n a1​,a2​…an​,求 ∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑n​j=i∑n​(k

2023NOIP A层联测26-competition

现在有一个题目数量为 m m m 的比赛,有一个团队想要来参加。 这个团队有 n n n 位选手,编号为 i i i 的选手能做第 l i ∼ r i l_i\sim r_i li​∼ri​ 道题,每一道题他都有 100 % 100\% 100% 的概率能做出来。 这个团队会随机派出一支队伍来参加这个比赛。 因为编号相邻的人关系更好,默契度也更高,所以说一个团队派出的队伍一直都是编