bzoj4373:算数天才与等差数列

算术天才⑨非常喜欢和等差数列玩耍。
有一天,他给了你一个长度为n的序列,其中第i个数为a[i]。
他想考考你,每次他会给出询问l,r,k,问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然,他还会不断修改其中的某一项。
为了不被他鄙视,你必须要快速并正确地回答完所有问题。
注意:只有一个数的数列也是等差数列。

第一行包含两个正整数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的个数来进行解密。

这道题用检验累加和/平方和的方式水过了。。最后发现是质数太大,乘起来溢出了。。。。。。

调了我三天(蠢哭了)

  1 #include <cstdio>
  2 #include <utility>
  3 using namespace std;
  4 typedef long long LL;
  5 typedef pair<LL, LL> ll;
  6 //#define debug
  7 
  8 #ifdef debug
  9 const LL maxn=105, prime=1e9+7;
 10 #else
 11 const LL maxn=3e5+5, prime=1e9+7;
 12 #endif
 13 LL n, m, cntyes;
 14 //可以捆绑♂到一起,这样查询更新都方便
 15 LL seg_sum[maxn*4], seg_sqr[maxn*4], maxm[maxn*4], minm[maxn*4];
 16 LL flag, *seg, POS, L, R, v;
 17 
 18 inline LL max(LL x, LL y) { return x<y?y:x; }
 19 inline LL min(LL x, LL y) { return x<y?x:y; }
 20 inline void swap(LL &x, LL &y) { LL t=x; x=y; y=t; }
 21 
 22 void modify(LL now, LL l, LL r){ //其实可以四个一起修改
 23     if (l>r||l>POS||r<POS) return;
 24     if (l==r) {
 25         if (flag==1) maxm[now]=minm[now]=v;
 26         if (flag==2) seg_sum[now]=v, seg_sqr[now]=v*v%prime;
 27         return;
 28     }
 29     LL mid=(l+r)>>1;
 30     modify(now<<1, l, mid); modify(now<<1|1, mid+1, r);
 31     if (flag==1){
 32         maxm[now]=max(maxm[now<<1], maxm[now<<1|1]);
 33         minm[now]=min(minm[now<<1], minm[now<<1|1]);
 34     }
 35     if (flag==2) {
 36         seg_sum[now]=(seg_sum[now<<1]+seg_sum[now<<1|1])%prime;
 37         seg_sqr[now]=(seg_sqr[now<<1]+seg_sqr[now<<1|1])%prime;
 38     }
 39 }
 40 
 41 ll query(LL now, LL l, LL r){ //其实可以四个一起查询
 42     if (l>r||l>R||r<L){
 43         if (flag==1) return make_pair(1e9, 0);
 44         if (flag==2) return make_pair(0, 0);
 45     }
 46     if (l>=L&&r<=R){
 47         if (flag==1)
 48             return make_pair(minm[now], maxm[now]);
 49         if (flag==2)
 50             return make_pair(seg_sum[now], seg_sqr[now]);
 51     }
 52     LL mid=(l+r)>>1;
 53     ll pair1, pair2;
 54     pair1=query(now<<1, l, mid); pair2=query(now<<1|1, mid+1, r);
 55     if (flag==1)
 56         return make_pair(min(pair1.first, pair2.first),
 57                          max(pair1.second, pair2.second));
 58     if (flag==2)
 59         return make_pair((pair1.first+pair2.first)%prime,
 60                          (pair1.second+pair2.second)%prime);
 61     return make_pair(-1, -1);
 62 }
 63 
 64 int main(){
 65     scanf("%lld%lld", &n, &m);
 66     LL value;
 67     for (LL i=1; i<=n; ++i){
 68         scanf("%lld", &value);
 69         flag=1, POS=i, v=value;
 70         modify(1, 1, n);
 71         flag=2, POS=i, v=value;
 72         modify(1, 1, n);
 73     }
 74     LL op, x, y, l, r, k;
 75     for (LL i=0; i<m; ++i){
 76         scanf("%lld", &op);
 77         if (op==1){
 78             scanf("%lld%lld", &x, &y);
 79             x^=cntyes, y^=cntyes;
 80             flag=1, POS=x, v=y;
 81             modify(1, 1, n);
 82             flag=2;
 83             modify(1, 1, n);
 84         }
 85         LL h, t, qsum, qsqr, vecsum, vecsqr;
 86         if (op==2){
 87             scanf("%lld%lld%lld", &l, &r, &k);
 88             l^=cntyes, r^=cntyes, k^=cntyes;
 89             if (l==r){
 90                 ++cntyes;
 91                 printf("Yes
");
 92                 continue;
 93             }
 94             if (l>r) swap(l, r);
 95             //查询最大最小值
 96             flag=1, L=l, R=r;
 97             ll re=query(1, 1, n);
 98             //h:等差队列最小值,t:等差队列最大值
 99             h=re.first, t=re.second;
100             if (k*(r-l)!=t-h){
101                 printf("No
"); continue;
102             }
103             //查询区间和
104             flag=2, L=l, R=r;
105             re=query(1, 1, n);
106             qsum=re.first, qsqr=re.second;
107             vecsum=(h+t)*(r-l+1)/2;
108             vecsum%=prime; //忘记模了。。
109             LL n=r-l+1;
110             //计算等差数列的平方和 h:a1 k:d l=r时要特判!!!
111             vecsqr=(h*h%prime*n%prime+
112                     (0+n-1)*n%prime*h%prime*k%prime)%prime+
113                     k*k%prime*((n-1)*n%prime*(2*n-1)/6%prime);
114             vecsqr%=prime;
115             if (qsum==vecsum&&qsqr==vecsqr){
116                 ++cntyes;
117                 printf("Yes
");
118             }
119             else printf("No
");
120         }
121     }
122     return 0;
123 }
原文地址:https://www.cnblogs.com/MyNameIsPc/p/7503131.html