首页 > 代码库 > bzoj 4373 算术天才⑨与等差数列
bzoj 4373 算术天才⑨与等差数列
4373: 算术天才⑨与等差数列
Time Limit: 10 Sec Memory Limit: 128 MBhttp://www.lydsy.com/JudgeOnline/problem.php?id=4373
Description
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
Input
第一行包含两个正整数n,m(1<=n,m<=300000)，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数a[i](0<=a[i]<=10^9)。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y(1<=x<=n，0<=y<=10^9)，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k(1<=l<=r<=n，0<=k<=10^9)，表示一个询问。
在本题中，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
区间是等差数列的条件：
1、区间内差分的gcd=公差
2、区间最大值-最小值=（区间长度-1）*公差
3、如果公差不等于0，区间内没有重复的数
条件3好像要记录这一个数上一次出现的位置，很麻烦
没有管条件3，竟然A了
线段树维护区间最大值，最小值，gcd即可
#include<cstdio>#include<algorithm>#define N 300001using namespace std;int n,m,tmp,x,p;int opl,opr,w;int g,big,small;int a[N];struct TREE{ struct node { int l,r; int maxn,minn,gcd; }tr[N*4]; int get_gcd(int a,int b) { return !b ? a : get_gcd(b,a%b); } int read() { int x=0,f=1; char c=getchar(); while(c<‘0‘||c>‘9‘) { if(c==‘-‘) f=-1; c=getchar(); } while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); } return x*f; } void up(int k) { tr[k].gcd=get_gcd(tr[k<<1].gcd,tr[k<<1|1].gcd); tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn); tr[k].minn=min(tr[k<<1].minn,tr[k<<1|1].minn); } void build(int k,int l,int r) { tr[k].l=l; tr[k].r=r; if(l==r) { a[l]=read(); tr[k].maxn=tr[k].minn=a[l]; tr[k].gcd=a[l]-a[l-1]; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void solve(int k) { if(tr[k].l>=opl&&tr[k].r<=opr) { if(x==2) { if(p==1) g=get_gcd(g,tr[k].gcd); else { big=max(big,tr[k].maxn); small=min(small,tr[k].minn); } } else { if(p==1) { tr[k].minn=tr[k].maxn=w; a[tr[k].l]=w; tr[k].gcd=a[tr[k].l]-a[tr[k].l-1]; } else tr[k].gcd=a[tr[k].l]-a[tr[k].l-1]; } return; } int mid=tr[k].l+tr[k].r>>1; if(opl<=mid) solve(k<<1); if(opr>mid) solve(k<<1|1); if(x==1) up(k); }}tree;int main(){ n=tree.read(); m=tree.read(); tree.build(1,1,n); while(m--) { scanf("%d",&x); if(x==2) { big=-1; small=2e9; g=0; opl=tree.read(); opr=tree.read(); w=tree.read(); opl^=tmp; opr^=tmp; w^=tmp; if(opl==opr) { puts("Yes"); tmp++; continue;} opl++; p=1; tree.solve(1); opl--; p=2; tree.solve(1); if(g<0) g=-g; if(g==w&&(opr-opl)*w==(big-small)) { puts("Yes"); tmp++; } else puts("No"); } else { opl=tree.read(); w=tree.read(); opl^=tmp; w^=tmp; opr=opl; p=1; tree.solve(1); if(opr!=n) { opl++; opr++; p=2; tree.solve(1); } } }}
无限RE,原因：
1、如果点i记录的是i与i-1的差，查询区间[l,r]的差分的gcd应该查询区间[l+1,r]，所以要特判l==r
2、修改点i，改了i点的差分，也改了点i+1的差分
bzoj 4373 算术天才⑨与等差数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。