글 읽기 - 세그트리에서 특정구간을 모두 특정 수로 update 시간복잡도

sgc109 7년 전 0

http://codeforces.com/contest/580/problem/E

이 문제를 풀고있는데 문자열의 구간들의 해시값으로 세그트리를 만들었는데

트리의 노드를 초기화해주는 함수와 query 함수는 O(lgn) 으로 구현했는데

특정 구간의 문자열을 모두 특정 문자로 바꾸어 세그트리를 update 해야 하는 부분은 아무리 생각해봐도 O(n) 로 밖에 구현하지못하겠습니다..

n 이 최대 100000인데 쿼리를 최대 100000번 날려서 모든 연산을 O(lgn) 으로 만들어야 AC 를 받을 수 있을 것같은데

세그트리의 특정 구간을 같은 수로 update 하는것이 O(lgn) 으로 가능한가요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <set>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

using namespace std;
	
typedef pair<long long, long long> pll;

const int INF = 0x3a3a3a3a;
const int MAX_N = 100000;

const long long Hash[2] = {1000000007,1000000009};

struct SegTree {
	vector<pll> rangeHash;
	int size;
	long long f[220];
	long long g[MAX_N][2];
	SegTree(string &s) {
		size = s.size();
		rangeHash.resize(4*size);
		FOR(i,10) f['0'+i] = i+1;
		g[0][0] = g[0][1] = 1;
		REP(i,1,size) {
			FOR(k,2) {
				g[i][k] = (g[i-1][k] * 257) % Hash[k];
			}
		}
		
		init(0,size-1,1,s);
	} 
	pll init(int nodeLeft, int nodeRight, int node, string &s) {
		if(nodeLeft == nodeRight) {
			return rangeHash[node] = mp(f[s[nodeLeft]], f[s[nodeLeft]]);
		}

		int nodeMid = (nodeLeft + nodeRight) >> 1;

		pll leftRange = init(nodeLeft, nodeMid, 2*node, s);
		pll rightRange = init(nodeMid+1, nodeRight, 2*node+1, s);

		int gI  = nodeRight-nodeMid;
		return rangeHash[node] = mp((leftRange.first*g[gI][0]+rightRange.first)%Hash[0],(leftRange.second*g[gI][1]+rightRange.second)%Hash[1]);
	}

	pll query(int nodeLeft, int nodeRight, int left, int right, int node) {
		if(nodeRight < left || right < nodeLeft) return mp(0,0);
		if(left <= nodeLeft && nodeRight <= right) return rangeHash[node];

		int nodeMid = (nodeLeft + nodeRight) >> 1;
		pll leftRange = query(nodeLeft, nodeMid, left, right, 2*node);
		pll rightRange = query(nodeMid+1, nodeRight, left, right, 2*node+1);

		int gI  = (nodeRight<=right?nodeRight:right)-nodeMid;
		gI = gI < 0 ? 0 : gI;
		return mp((leftRange.first*g[gI][0]+rightRange.first)%Hash[0],(leftRange.second*g[gI][1]+rightRange.second)%Hash[1]);
	}

	pll update(int nodeLeft, int nodeRight, int left, int right, int node, char val) {
		if(nodeLeft == nodeRight && left <= nodeLeft && nodeRight <= right) return rangeHash[node] = mp(f[val],f[val]);
		if(right < nodeLeft || nodeRight < left) return rangeHash[node];

		int nodeMid = (nodeLeft + nodeRight) >> 1;
		pll leftRange = update(nodeLeft, nodeMid, left, right, 2*node, val);
		pll rightRange = update(nodeMid+1, nodeRight, left, right, 2*node+1, val);

		int gI  = nodeRight-nodeMid;
		return rangeHash[node] = mp((leftRange.first*g[gI][0]+rightRange.first)%Hash[0],(leftRange.second*g[gI][1]+rightRange.second)%Hash[1]);	
	}
	pll query(int left, int right) {
		return query(0,size-1,left,right,1);
	}
	pll update(int left, int right, char val) {
		return update(0,size-1,left,right,1,val);
	}
};

int main() {
	setbuf(stdout,NULL);
	int n,m,k;
	inp3(n,m,k);
	string s;
	cin >> s;
	SegTree segTree(s);
	FOR(t,m+k) {
		int x,l,r,d;
		inp4(x,l,r,d);
		--l;--r;
		if(x==1) {
			segTree.update(l,r,'0'+d);
		}
		else if(x==2) {
			pll p1 = segTree.query(l,r-d);
			pll p2 = segTree.query(l+d,r);
			if(p1.first*Hash[1]+p1.second == p2.first*Hash[1]+p2.second) printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}

smu201111192 7년 전 0

lazy propagation 쓰시면되지않나요?

sgc109 7년 전 0

@smu201111192 아 그런게 있었군요.. 검색해보겠습니다 감사합니다!

smu201111192 7년 전 1

네 파이팅요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그트리에서 특정구간을 모두 특정 수로 update 시간복잡도

sgc109 7년 전 0

smu201111192 7년 전 0

sgc109 7년 전 0

smu201111192 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말