공약 수열

공약 수열
시간 제한: 1 Sec 메모리 제한: 256 MB
제목 설명 은 데이터 구 조 를 설계 합 니 다. 정수 수열 a 를 지정 합 니 다.0, a_1, …, a_{n - 1}, 다음 두 가지 동작 을 지원 해 야 합 니 다: 1. MODIFY id x: a{id} x. 2. QUERY x: 최소 정수 p (0 < = p < n) 를 구하 고 gcd (a 0, a 1,..., a p) * XOR (a 0, a 1,..., a p) = x. 그 중에서 XOR (a 0, a 1,..., a p) 는 a0, a_1, …, a_p 의 이 또는 화, gcd 는 최대 공약수 입 니 다.
입력 데 이 터 를 입력 하 는 첫 줄 에는 정수 n 이 포함 되 어 있 습 니 다. 다음 줄 에는 n 개의 정수 a 가 포함 되 어 있 습 니 다.0, a_1, …, a_{n - 1}. 다음 줄 에는 질문 의 개 수 를 나타 내 는 정수 q 가 포함 되 어 있 습 니 다.이후 q 줄, 줄 마다 질문 이 포함 되 어 있 습 니 다.형식 은 제목 에서 말 한 바 와 같다.
출력 은 모든 QUERY 질문 에 대해 단독 줄 에서 결 과 를 출력 합 니 다.이러한 p 가 존재 하지 않 는 다 면 출력 no.
샘플 입력 10 1353600 5821200 10752000 16704000 3729600 6844320 12544000 59400 640 10 MODIFY 7 20321280 QUERY 162343680 QUERY 1832232960000 MODIFY 0 92160 QUERY 1234567 QUERY 3989856000 QUERY 833018560 MODIFY 3 8600 MODIFY 5 5306112 QUERY 148900352
샘플 출력 60 no 28
【 데이터 규모 와 약정 】 30% 의 데이터 에 대해 n < = 10000, q < = 1000. 100% 의 데이터 에 대해 n < = 100000, q < = 10000, ai < = 10 ^ 9 (0 < = i < n), QUERY x 의 x < = 10 ^ 18, MODIFY id x 의 0 < = id < n, 1 < = x < = 10 ^ 9.
출처: heoi 2015 day 1
해제
선분 트 리 로 쓰 려 고 했 는데 선분 트 리 가 안 나 오 더 라 고요.나중에 뇌 를 고 쳐 보 니 덩어리 가 지나 갈 수 있다 는 것 을 발견 하고 덩어리 를 나 누 었 다.여기 서 결론 을 내 려 야 합 니 다. 한 단락 에서 gcd 는 최대 logn 가지 만 있 습 니 다.그래서 각 · 블록 에 대해 gcd 가 같 으 면 2 분 의 답 입 니 다.또 알 고 있 습 니 다. sumi ^ tagi (태그) * gcd (tmp, gcdi) = x, 이 식 을 그 어 sumi 의 값 을 구하 고 2 분, 해시, map 같은 방법 으로 구간 에 이 사람의 숫자 가 있 는 지 찾 아 보 세 요.gcd 의 서로 다른 구간 에 대해 폭력 처 리 는 최대 logn 개 구간 만 있 기 때문에 총 복잡 도 는 n * sqrt (n) * logn 이다.
코드

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define N 100010
#define M 350
#define ll long long
using namespace std;
int n,q,num,s[N],sum[N],blo[N],l[M],r[M],g[M],tag[M];
struct node{
  int num,pos;
  bool operator<(const node &x)
  const{return num<x.num||(num==x.num&&pos<x.pos);}
}t[N];

int gcd(int a,int b)
{
  if(!b)return a;
  return gcd(b,a%b);
}

int main()
{
  int x,y;ll a;char str[10];
  scanf("%d",&n);num=sqrt(n);
  for(int i=1;i<=n;i++)scanf("%d",&s[i]);
  for(int i=1;i<=num;i++)
  {
    l[i]=r[i-1]+1;r[i]=min(l[i]+num,n);
    for(int j=l[i];j<=r[i];j++)
    {
      blo[j]=i;sum[j]=sum[j-1]^s[j];
      g[i]=gcd(g[i],s[j]);t[j]=(node){sum[j],j};
    }
    sort(t+l[i],t+r[i]+1);
  }
  scanf("%d",&q);
  while(q--)
  {
    scanf(" %s",str);
    if(str[0]=='M')
    {
      scanf("%d%d",&x,&y);x++;
      int pos=blo[x];y^=s[x];s[x]^=y;g[pos]=0;
      for(int i=l[pos];i<=r[pos];i++)g[pos]=gcd(g[pos],s[i]);
      for(int i=pos+1;i<=num;i++)tag[i]^=y;
      for(int i=l[pos];i<x;i++)t[i]=(node){sum[i],i};
      for(int i=x;i<=r[pos];i++)sum[i]^=y,t[i]=(node){sum[i],i};
      sort(t+l[pos],t+r[pos]+1);
    }
    else
    {
      int ans=0;
      scanf("%lld",&a);
      for(int i=1,tmp=0;i<=num&&!ans;i++)
      {
        if(gcd(tmp,s[l[i]])==gcd(tmp,g[i]))
        {
          int tot=(a/gcd(tmp,g[i]))^tag[i];
          int tp=lower_bound(t+l[i],t+r[i]+1,(node){tot,0})-t;
          tmp=gcd(tmp,g[i]);
          if(t[tp].num!=tot)continue;
          ans=t[tp].pos;
        }
        else
        {
          if(tag[i])
          {
            for(int j=l[i];j<=r[i];j++)
              sum[j]^=tag[i],t[j]=(node){sum[j],j};
            tag[i]=0;sort(t+l[i],t+r[i]+1);
          }
          for(int j=l[i];j<=r[i];j++)
          {
            if((ll)sum[j]*gcd(tmp,s[j])==a){ans=j;break;}
            tmp=gcd(tmp,s[j]);
          }
        }
      }
      if(!ans)printf("no
");
      else printf("%d
",ans-1);
    }
  }
  return 0;
}