首页 > 代码库 > 【BZOJ4373】算术天才⑨与等差数列 [线段树]
【BZOJ4373】算术天才⑨与等差数列 [线段树]
算术天才⑨与等差数列
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
Input
第一行包含两个正整数n,m，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数a[i]。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k，表示一个询问。
在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。
Output
输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。
Sample Input
5 3
1 3 2 5 6
2 1 5 1
1 5 4
2 1 5 1
1 3 2 5 6
2 1 5 1
1 5 4
2 1 5 1
Sample Output
No
Yes
Yes
HINT
1<=n,m<=300000, 0<=a[i]<=10^9, 1<=x<=n，0<=y<=10^9, 1<=l<=r<=n, 0<=k<=10^9
Solution
显然，如果可以组成等差数列，首项必定是区间最小值。这样我们就知道了要求的等差数列的首项和公差。
一个首先的想法就是：我们判断一下区间和是否等于所要求的等差数列的和。
但是这样显然是不够的，那么怎么办呢？我们试想：能否求出所要求的等差数列的平方和？
显然公差为 1 的时候用平方和公式计算，剩下公差不是 1 的时候我们轻易推一下式子即可。
那么我们只要用线段树维护一下：区间最小值、区间和、区间平方和即可，资磁单点修改。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<queue> 9 using namespace std; 10 typedef long long s64; 11 12 const int ONE = 500005; 13 const int INF = 1e9+7; 14 15 int n, T; 16 s64 a[ONE]; 17 int opt, x, y, d; 18 int num; 19 20 struct power 21 { 22 s64 sumx, sumxx, minx; 23 }Node[ONE * 4], res; 24 25 int get() 26 { 27 int res=1,Q=1;char c; 28 while( (c=getchar())<48 || c>57 ) 29 if(c==‘-‘)Q=-1; 30 res=c-48; 31 while( (c=getchar())>=48 && c<=57 ) 32 res=res*10+c-48; 33 return res*Q; 34 } 35 36 void Renew(int i) 37 { 38 int a = i<<1, b = i<<1|1; 39 Node[i].sumx = Node[a].sumx + Node[b].sumx; 40 Node[i].sumxx = Node[a].sumxx + Node[b].sumxx; 41 Node[i].minx = min(Node[a].minx, Node[b].minx); 42 } 43 44 void Build(int i, int l, int r) 45 { 46 Node[i].minx = INF; 47 if(l == r) 48 { 49 Node[i].minx = a[l]; 50 Node[i].sumx = a[l]; 51 Node[i].sumxx = a[l] * a[l]; 52 return; 53 } 54 55 int mid = l + r >> 1; 56 Build(i<<1, l, mid); Build(i<<1|1, mid+1, r); 57 Renew(i); 58 } 59 60 void Update(int i, int l, int r, int L, s64 x) 61 { 62 if(l > r) return; 63 if(L == l && l == r) 64 { 65 Node[i].minx = x; 66 Node[i].sumx = x; 67 Node[i].sumxx = x * x; 68 return; 69 } 70 71 int mid = l + r >> 1; 72 if(L <= mid) Update(i<<1, l, mid, L, x); 73 else Update(i<<1|1, mid+1, r, L, x); 74 Renew(i); 75 } 76 77 void Query(int i, int l, int r, int L, int R) 78 { 79 if(L <= l && r <= R) 80 { 81 res.minx = min(res.minx, Node[i].minx); 82 res.sumx += Node[i].sumx; 83 res.sumxx += Node[i].sumxx; 84 return; 85 } 86 87 int mid = l + r >> 1; 88 if(L <= mid) Query(i<<1, l, mid, L, R); 89 if(mid+1 <= R) Query(i<<1|1, mid+1, r, L, R); 90 } 91 92 s64 Calc_sumx(s64 a0, s64 n, s64 d) 93 { 94 s64 an = a0 + (n-1) * d; 95 return (a0 + an) * n / 2; 96 } 97 98 s64 Calc_sumxx(s64 a0, s64 n, s64 d) 99 {100 s64 item1 = n * a0 * a0;101 s64 item2 = 2 * a0 * d * n * (n-1) / 2;102 s64 item3 = d * d * (n * (n+1) * (2*n+1) / 6 - n*n);103 return item1 + item2 + item3;104 }105 106 int main()107 {108 n = get(); T = get();109 for(int i=1; i<=n; i++)110 a[i] = get();111 Build(1, 1, n);112 113 while(T--)114 {115 opt = get();116 x = get() ^ num; y = get() ^ num;117 118 if(opt == 1)119 {120 Update(1, 1, n, x, y);121 continue;122 }123 else124 {125 d = get() ^ num;126 res.minx = INF;127 res.sumx = res.sumxx = 0;128 Query(1, 1, n, x, y);129 130 if(res.sumx == Calc_sumx(res.minx, y-x+1, d))131 if(res.sumxx == Calc_sumxx(res.minx, y-x+1, d))132 {133 printf("Yes\n");134 num++;135 continue;136 }137 138 printf("No\n");139 }140 }141 142 }
【BZOJ4373】算术天才⑨与等差数列 [线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。