首页 > 代码库 > [BZOJ4373]算术天才⑨与等差数列
[BZOJ4373]算术天才⑨与等差数列
思路：
构造等差数列的条件：
1、区间内所有数差分的$gcd=x$
2、区间内$max-min=(r-l)*k$
3、区间内数字不相同
线段树维护最大值，最小值以及差分。
对于每次询问判断上述三种情况，如果满足则说明可以构成等差数列。
需要特判的情况：
1、$k=0$，此时条件3不需要满足
2、$l=r$，此时数列（单个数字）一定能构成等差数列
然而由于数据比较水，所以条件3不判断也没关系。
实测加上条件3判断8936ms，不判断2836ms。
另外有一种hash的做法。
Rank1在hash的基础上还用了zkw线段树，只跑了740ms。
1 #include<set> 2 #include<map> 3 #include<cmath> 4 #include<cstdio> 5 #include<cctype> 6 #include<utility> 7 #include<algorithm> 8 inline int getint() { 9 char ch; 10 while(!isdigit(ch=getchar())); 11 int x=ch^‘0‘; 12 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 13 return x; 14 } 15 const int N=300001,inf=0x7fffffff; 16 int a[N]={0}; 17 class SegmentTreeM { 18 #define _left <<1 19 #define _right <<1|1 20 private: 21 int max[N<<2],min[N<<2]; 22 void push_up(const int p) { 23 max[p]=std::max(max[p _left],max[p _right]); 24 min[p]=std::min(min[p _left],min[p _right]); 25 } 26 public: 27 void build(const int p,const int b,const int e) { 28 if(b==e) { 29 max[p]=min[p]=a[b]; 30 return; 31 } 32 int mid=(b+e)>>1; 33 build(p _left,b,mid); 34 build(p _right,mid+1,e); 35 push_up(p); 36 } 37 void modify(const int p,const int b,const int e,const int x) { 38 if(b==e) { 39 max[p]=min[p]=a[x]; 40 return; 41 } 42 int mid=(b+e)>>1; 43 if(x<=mid) modify(p _left,b,mid,x); 44 if(x>mid) modify(p _right,mid+1,e,x); 45 push_up(p); 46 } 47 std::pair<int,int> query(const int p,const int b,const int e,const int l,const int r) { 48 if((l==b)&&(e==r)) return std::make_pair(max[p],min[p]); 49 int mid=(b+e)>>1; 50 std::pair<int,int> ans=std::make_pair(0,inf); 51 if(l<=mid) { 52 std::pair<int,int> s=query(p _left,b,mid,l,std::min(mid,r)); 53 ans=std::make_pair(std::max(ans.first,s.first),std::min(ans.second,s.second)); 54 } 55 if(r>mid) { 56 std::pair<int,int> s=query(p _right,mid+1,e,std::max(mid+1,l),r); 57 ans=std::make_pair(std::max(ans.first,s.first),std::min(ans.second,s.second)); 58 } 59 return ans; 60 } 61 bool check(const int n,const int l,const int r,const int k) { 62 std::pair<int,int> t=query(1,1,n,l,r); 63 return t.first-t.second==(r-l)*k; 64 } 65 }; 66 SegmentTreeM m_t; 67 int d[N]={0}; 68 class SegmentTreeGCD { 69 #define _left <<1 70 #define _right <<1|1 71 private: 72 int val[N<<2]; 73 int gcd(const int x,const int y) { 74 if(!x&&!y) return 0; 75 return y?gcd(y,x%y):x; 76 } 77 void push_up(const int p) { 78 val[p]=gcd(val[p _left],val[p _right]); 79 } 80 public: 81 void build(const int p,const int b,const int e) { 82 if(b==e) { 83 val[p]=d[b]; 84 return; 85 } 86 int mid=(b+e)>>1; 87 build(p _left,b,mid); 88 build(p _right,mid+1,e); 89 push_up(p); 90 } 91 void modify(const int p,const int b,const int e,const int x) { 92 if(b==e) { 93 val[p]=d[x]; 94 return; 95 } 96 int mid=(b+e)>>1; 97 if(x<=mid) modify(p _left,b,mid,x); 98 if(x>mid) modify(p _right,mid+1,e,x); 99 push_up(p);100 }101 void modify(const int p,const int b,const int e,const int x,const int y) {102 int mid=(b+e)>>1;103 if(y<=mid) modify(p _left,b,mid,x,y);104 if(x>mid) modify(p _right,mid+1,e,x,y);105 if((x==mid)&&(y==mid+1)) modify(p _left,b,mid,x),modify(p _right,mid+1,e,y);106 push_up(p);107 }108 int query(const int p,const int b,const int e,const int l,const int r) {109 if((l==b)&&(e==r)) return val[p];110 int ans=0;111 int mid=(b+e)>>1;112 if(l<=mid) ans=gcd(ans,query(p _left,b,mid,l,std::min(mid,r)));113 if(r>mid) ans=gcd(ans,query(p _right,mid+1,e,std::max(mid+1,l),r));114 return ans;115 }116 bool check(const int n,const int l,const int r,const int k) {117 return query(1,1,n-1,l,r-1)==k;118 }119 };120 SegmentTreeGCD gcd_t;121 /*class Sets {122 private:123 std::map<int,std::set<int> > pre;124 public:125 void erase(const int x) {126 pre[a[x]].erase(x);127 }128 void insert(const int x) {129 pre[a[x]].insert(x);130 }131 bool check(const int l,const int r) {132 for(int i=l;i<=r;i++) {133 std::set<int>::iterator p=pre[a[i]].find(i);134 if(p==pre[a[i]].end()||p==pre[a[i]].begin()) continue;135 if(*--p>=l) return false;136 }137 return true;138 }139 };140 Sets s;*/141 inline bool check(const int n,const int l,const int r,const int k) {142 if(l==r) return true;143 if(!k) return m_t.check(n,l,r,k)&&gcd_t.check(n,l,r,k);144 return m_t.check(n,l,r,k)&&gcd_t.check(n,l,r,k)/*&&s.check(l,r)*/;145 }146 int main() {147 int n=getint(),m=getint();148 for(int i=1;i<=n;i++) {149 a[i]=getint();150 if(i>1) d[i-1]=abs(a[i]-a[i-1]);151 //s.insert(i);152 }153 m_t.build(1,1,n);154 gcd_t.build(1,1,n-1);155 int count=0;156 while(m--) {157 int op=getint();158 if(op==1) {159 int x=getint()^count;160 //s.erase(x);161 a[x]=getint()^count;162 //s.insert(x);163 m_t.modify(1,1,n,x);164 if(x!=n) d[x]=abs(a[x+1]-a[x]);165 if(x>1) d[x-1]=abs(a[x]-a[x-1]);166 if(x==n) gcd_t.modify(1,1,n-1,x-1);167 if(x<=1) gcd_t.modify(1,1,n-1,x);168 if((x>1)&&(x!=n)) gcd_t.modify(1,1,n-1,x-1,x);169 }170 if(op==2) {171 int l=getint()^count,r=getint()^count,k=getint()^count;172 if(check(n,l,r,k)) {173 puts("Yes");174 count++;175 }176 else {177 puts("No");178 }179 }180 }181 return 0;182 }
[BZOJ4373]算术天才⑨与等差数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。