2018 - 10 - 14 보급 시 뮬 레이 션 "해시 키 (hash)

비둘기 가 돌아오다
성명: 코드 를 베 끼 려 면 당신 자신 만 해 칠 수 있 습 니 다...
오늘 여러분 께 사고 문 제 를 보 여 드 리 겠 습 니 다.
해시 키 (hash)
제목 설명

Marser  hash    ，          hash   ……

Marser   hash            ，    i    i mod p。        ，       ，            i mod p。           p   r，               。  ，Marser               ，                  。

  Marser q   ，             。       ，          。      1s         ，Marser   hotwords     。

입력 형식

   hash.in  。

       n，q，           。

   n   ，       。

   m ，      opt，x，y；

 opt=1，    mod x ，       y    。

 opt=2，     x    y。

출력 형식

     hash.out 。

본보기
샘플 입력 1

10 5
1 2 3 4 5 6 7 8 9 10
1 2 1
2 1 20
1 3 1
2 5 1
1 5 0

샘플 출력 1

25
41
11

우선, 우 리 는 이것 이 물 문제 라 는 것 을 발견 했다.
아래 코드 를 가볍게 쓰 세 요.

#include 
using namespace std;
int a[100005];

int main() {
    int n, m;
    freopen("hash.in","r",stdin);
    freopen("hash.out","w",stdout);//      
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        if (x == 1) {
            int x1, x2, ans = 0;
            scanf("%d%d", &x1, &x2);
            for (int i = x2; i <= n; i += x1) {  //         ，    x1      ；
                ans += a[i]; 
            }
            printf("%d
", ans);
        }
        if (x == 2) {
            int x1, x2;
            scanf("%d%d", &x1, &x2);
            a[x1] = x2;  //  
        }
    }
}

그리고 우 리 는 발견 했다.
가볍게 시간 을 초과 하 다.
30 점 이 라 니!!!
크 크, 본론 으로 들 어가 자, 우 리 는 100 점 의 코드 를 토론 하기 시작 했다.
(읊 기 시작)
Frist：
우 리 는 시간의 복잡 도 를 계산 해 야 한다.
원 코드 시간 복잡 도 는 O (n + mn / x1) 입 니 다.
그래서 우리 의 코드 는 반드시 이 시간의 복잡 도 보다 작 아야 한다.
second
우 리 는 어쨌든 원래 코드 의 시간 복잡 도 는 줄 일 수 없다 는 것 을 알 게 되 었 다. 적어도 나 는 생각 하지 못 했다.그래서:
새로운 길 을 개척 하 다.
곰 곰 이 생각해 보면 어렵 지 않다. 만약 에 우리 가 x1, x2 를 읽 을 때 ans 를 직접 출력 할 수 있다 면 시간 복잡 도 는 크게 떨 어 질 것 이다.
그러면 우 리 는 어떻게 해야만 이런 조작 을 실현 할 수 있 습 니까?
먼저, sum 이라는 2 차원 배열 을 정의 합 니 다. sum [i] [j] 는 모든 모 i 여 j 의 수의 총 계 를 표시 합 니 다.
a [i] 를 하나 더 입력 한 후 반복 해서 옮 겨 다 니 며 코드 는 다음 과 같 습 니 다.

for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		for(int j=1;j<n;++j){
			sum[j][i%j]+=a[i];  // j (i%j);
		}
	}

이렇게 하면 우 리 는 사실 입 출력 을 달성 할 수 있 습 니 다!!
그러나 우 리 는 시간 복잡 도 O = (N + mn) (왜 mn 입 니까? 우리 가 값 을 바 꿀 때 sum 배열 의 것 도 바 꿔 야 하기 때 문 입 니 다).
그리고 우 리 는 신기 하 게 도 시간 복잡 도가 원래 보다 더 크다 는 것 을 발견 했다!
그렇다면 우리 가 모든 값 을 옮 겨 다 니 지 않 고 log (n) 만 옮 겨 다 니 며 x1 > log (n) 의 상황 을 첫 번 째 방법 으로 연산 한다 면??
재 계산 시간 복잡 도: O = (n * log (m) + MAX (mn / x1, mn);
간단하게: O = (n * log (m) + mn / x1);
그리고 우 리 는 남 은 테스트 포 인 트 를 넘 길 수 있어!!코드 올 려!!:
다시 한 번 말씀 드 리 지만 코드 를 베 끼 려 면 당신 자신 만 해 칠 수 있 습 니 다...

#include
using namespace std;
int a[1000005],sum[1005][1005]; //sum[i][j]      i j    ； 

int main(){
	freopen("hash.in","r",stdin);
    freopen("hash.out","w",stdout);  //       
	int n,m;
	scanf("%d%d",&n,&m);
	int num=sqrt(n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		for(int j=2;j<num;j++){
			sum[j][i%j]+=a[i];   // sum    ，  j  i      ； 
		}
	}
	for(int i=1;i<=m;++i){
		int x;
		scanf("%d",&x);
		if(x==1){
			int x1,x2,ans=0;
			scanf("%d%d",&x1,&x2);
			if(x1<num){//  x1
				printf("%d
",sum[x1][x2]);  //       sum     ； 
			}
			else{							
				for(int i=x2;i<=n;i+=x1){			//   ； 
					ans+=a[i]; 
				}
				printf("%d
",ans);	
			}
		}
		if(x==2){
			int x1,x2;
			scanf("%d%d",&x1,&x2);
			for(int i=1;i<=num;i++)
                sum[i][x1%i]=sum[i][x1%i]-a[x1]+x2;  //  sum  ， a[x1]   x2,   sum     ； 
            a[x1]=x2;  // a[i]      ； 
		}
	}
}