BZOJ 4028: [HEOI 2015] 공약 수열

제목 대의: 데이터 구 조 를 설계 합 니 다. 정수 수열 a0, 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 는 최대 공약수 입 니 다.
접두사 gcd * 접두사 가 다 르 거나 = 주어진 값 을 원 하 는 이상 자 연 스 러 운 생각 은 모든 접두사 gcd 의 값 과 접두사 가 다 르 거나 값 을 기록 하 는 것 입 니 다. 이 단 계 는 블록 을 사용 할 수 있 습 니 다. gcd 의 값 이 매우 적 기 때문에 물 어 볼 때마다 이 블록 이 이전 블록 의 gcd 와 다 르 면 폭력 적 으로 이 블록 을 한 번 뛰 어 다 닐 수 있 습 니 다.만약 같다 면 이 블록의 모든 접두사 gcd = 이전 블록의 gcd 를 증명 합 니 다. 우 리 는 해시 표 로 이 블록의 모든 접두사 가 다 르 거나 값 이 존재 하 는 지 직접 확인 합 니 다.수정 작업 에 대해 서 는 각각 하나의 배열 을 열 어 자신의 gcd 를 기록 합 니 다. 한 점 의 수정 이기 때문에 수 정 된 폭력 을 고치 고 나머지 는 자신의 gcd 와 앞의 gcd 로 구하 면 됩 니 다.다 르 거나 수정 할 때 우 리 는 차이 가 있 거나 교환 율 이 있다 는 것 을 알 고 있 기 때문에 표 시 를 하나 열 어 차이 나 값 의 변동 을 기록 합 니 다. 앞에서 조회 할 때 차이 나 표 시 를 기억 합 니 다...............................................

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100000+10;
const int maxm=330;
map<int,int> mp[maxm];
int hm[maxm],sumxor[maxm],sumgcd[maxm],gcd1[maxm],a[maxn],tag[maxn];
int n,m,belong[maxn],bl[maxn],br[maxn],size;
long long x;
char op[10];
int main()
{
  //freopen("4028.in","r",stdin);
  //freopen("4028.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  while(size*size<=n) size++;
  for(int i=1;i<=size;i++)
  {
    int l=(i-1)*size+1,r=min(n,i*size);
    for(int j=l;j<=r;j++)
      belong[j]=i;
    bl[i]=l;br[i]=r;
  }
  for(int i=1;i<=size;i++)
  {
    if(i==1) sumxor[i]=sumgcd[i]=a[1];
    else sumxor[i]=sumxor[i-1],sumgcd[i]=sumgcd[i-1];
    int l=bl[i];if(i==1) l++;
    for(int j=l;j<=br[i];j++)
    {
      sumxor[i]^=a[j];
      if(!mp[i][sumxor[i]]) mp[i][sumxor[i]]=j;
      sumgcd[i]=__gcd(sumgcd[i],a[j]);
    }
  }
  for(int i=1;i<=size;i++)
  {
    gcd1[i]=a[bl[i]];
    for(int j=bl[i]+1;j<=br[i];j++)
      gcd1[i]=__gcd(gcd1[i],a[j]);
  }
  scanf("%d",&m);
  for(int i=1;i<=m;i++)
  {
    scanf("%s%lld",&op,&x);
    if(op[0]=='Q')
    {
      int hm,gcd;hm=gcd=a[1];int res=1000000000;
      if((long long)hm*gcd==x) res=1;
      for(int j=2;j<=br[1];j++)
      {
        hm=hm^a[j];
        gcd=__gcd(gcd,a[j]);
        if((long long)hm*gcd==x)
        {
          res=min(res,j);
          break;
        }
      }
      for(int j=2;j<=size;j++)
        if(sumgcd[j]!=sumgcd[j-1])
        {
          hm=sumxor[j-1];gcd=sumgcd[j-1];
          for(int k=bl[j];k<=br[j];k++)
          {
            hm=hm^a[k];gcd=__gcd(gcd,a[k]);
            if((long long)hm*gcd==x)
            {
              res=min(res,k);
              break;
            }
          }
        }
        else if(x%sumgcd[j]==0)
        {
          long long t=x/sumgcd[j];t^=tag[j];
          if(mp[j][t])
          {
            res=min(res,mp[j][t]);
            break;
          }
        }
        if(res<1000000000) printf("%d
",res-1);
        else printf("no
");
    }
    else
    {
      int v;scanf("%d",&v);int p=x+1;int t=a[p];
      a[p]=v;int hh=belong[p];
      if(hh==1)
      {
        mp[1].clear();tag[1]=0;
        sumxor[1]=sumgcd[1]=a[1];mp[1][a[1]]=1;
        for(int j=2;j<=size;j++)
        {
          sumxor[1]^=a[j];
          sumgcd[1]=__gcd(sumgcd[1],a[j]);
          if(!mp[1][sumxor[1]]) mp[1][sumxor[1]]=j;
        }
        gcd1[1]=a[1];for(int j=2;j<=size;j++) gcd1[1]=__gcd(gcd1[1],a[j]);
      }
      else
      {
        sumxor[hh]=sumxor[hh-1];sumgcd[hh]=sumgcd[hh-1];mp[hh].clear();tag[hh]=0;
        for(int j=bl[hh];j<=br[hh];j++)
        {
          sumxor[hh]^=a[j];
          sumgcd[hh]=__gcd(sumgcd[hh],a[j]);
          if(!mp[hh][sumxor[hh]]) mp[hh][sumxor[hh]]=j;
        }
        gcd1[hh]=a[bl[hh]];for(int j=bl[hh]+1;j<=br[hh];j++) gcd1[hh]=__gcd(gcd1[hh],a[j]);
      }
      for(int j=hh+1;j<=size;j++) tag[j]^=t^v,sumxor[j]^=t^v;
      for(int j=hh+1;j<=size;j++) sumgcd[j]=__gcd(sumgcd[j-1],gcd1[j]);
    }
  }
  return 0;
}