Poj 3468 A Integers 관련 8가지 간단한 문제 해결 방법

16200 단어
1. 반복 세그먼트 트리, 완료 시 표시:
#include <stdio.h>
#include <stdlib.h>

using namespace std;

#define N 100009
#define lx (x<<1)
#define rx (x<<1 | 1)
#define MID ((l+r)>>1)
#define LL long long
int n,q;
char c;
int a,b,d;

int A[N];
LL S[N<<2];
LL D[N<<2];

void pushUp(int x)
{
    S[x] = S[lx] + S[rx];
}

void pushDown(int l,int r,int x)
{
    if(D[x])
    {
        D[lx]+=D[x];
        D[rx]+=D[x];
        S[lx]+=(MID-l+1)*D[x];
        S[rx]+=(r-MID)*D[x];
        D[x] = 0;
    }
}

void build(int l,int r,int x)
{
    if(l == r)
    {
        S[x] = A[l];
        return;
    }

    build(l,MID,lx);
    build(MID+1,r,rx);
    pushUp(x);
}
LL query(int L,int R,int l,int r,int x)
{
    LL ans = 0;
    if(L<=l && r<=R)
    {
        return S[x];
    }
    pushDown(l,r,x);
    if(L<=MID) ans += query(L,R,l,MID,lx);
    if(R>=MID+1) ans += query(L,R,MID+1,r,rx);
    return ans;
}

void update(int L,int R,int d,int l,int r,int x)
{
    if(L<=l && r<=R)
    {
        D[x] += d;
        S[x] += (r - l + 1)*d;
        return;
    }
    pushDown(l,r,x);
    if(L<=MID) update(L,R,d,l,MID,lx);
    if(MID+1<=R) update(L,R,d,MID+1,r,rx);
    pushUp(x);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
    }
    build(1,n,1);
    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",query(a,b,1,n,1));
        }
        else
        {
            scanf("%d%d",&a,&b);
            scanf("%d",&d);
            update(a,b,d,1,n,1);
        }
    }
    return 0;
}

2. 반복 세그먼트 트리, 미완성 시 태그:
#include <stdio.h>
#include <stdlib.h>

using namespace std;

#define N 100009
#define lx (x<<1)
#define rx (x<<1 | 1)
#define MID ((l+r)>>1)
#define LL long long

int n,q;
char c;
int a,b,d;

int A[N];
LL S[N<<2];
LL D[N<<2];

void build(int l,int r,int x)
{
    if(l == r)
    {
        S[x] = A[l];
        return;
    }

    build(l,MID,lx);
    build(MID+1,r,rx);
    S[x] = S[lx] + S[rx];
}
LL getSum(int l,int r,int x)
{
    if(a<=l && r<=b)
    {
        return S[x] + D[x]*(r-l+1);
    }
    if(D[x])
    {
        D[lx]+=D[x];
        D[rx]+=D[x];
        S[x]+=D[x]*(r-l+1);
        D[x] = 0;
    }
    return (a<=MID ? getSum(l,MID,lx) : 0) + ((MID+1)<=b ? getSum(MID+1,r,rx) : 0);
}
void update(int l,int r,int x)
{
    if(a<=l && r<=b)
    {
        D[x]+=d;
        return ;
    }
    // 
    if(D[x])
    {
        D[lx]+=D[x];
        D[rx]+=D[x];
        D[x] = 0;
    }
    if(a<=MID)
    {
        update(l,MID,lx);
    }
    if(MID+1<=b)
    {
        update(MID+1,r,rx);
    }
    S[x] = S[lx] + S[rx] + D[lx]*(MID-l+1) + D[rx]*(r-MID);
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
    }
    build(1,n,1);
    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",getSum(1,n,1));
        }
        else
        {
            scanf("%d%d",&a,&b);
            scanf("%d",&d);
            update(1,n,1);
        }
    }
    return 0;
}

3. 비귀속 세그먼트 트리(대량 업데이트, 구간 구화):
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
#define N 100009
#define LL long long
int M;// 

int A[N];
LL S[1<<18];// N 
LL D[1<<18];


int n,q,a,b,d;
char c;

void build()
{
    for(int i=2*M-1;i>0;i--)
    {
        if(i>=M)
        {
            S[i] = A[i-M];
        }
        else
        {
            S[i] = S[i<<1] + S[(i<<1)| 1];
        }
    }
}

LL getSum()
{
    LL sum = 0;
    int num_a, num_b;
    int step = 0;
    num_a = num_b = 0;
    for(a=a+M-1,b=b+M+1;a^b^1;a>>=1,b>>=1)
    {

        // 
        if(~a&1)
        {
            sum+=S[a^1];
            num_a+=(1<<step);
        }
        // 
        if(b&1)
        {
            sum+=S[b^1];
            num_b+=(1<<step);
        }
        sum+=num_a * D[a>>1];
        sum+=num_b * D[b>>1];
        step++;
    }
    for(a>>=1;a>0;a>>=1)
    {
        sum+=(num_a + num_b)*D[a];
    }
    return sum;
}
void update()
{
    int num_a,num_b;
    int step = 0;
    num_a = num_b = 0;
    for(a=a+M-1,b=b+M+1;a^b^1;a>>=1,b>>=1)
    {

        // a 
        if(~a&1)
        {
            S[a^1] +=(1<<step) * d;
            D[a^1] +=d;
            num_a+=(1<<step);
        }
        // b 
        if(b&1)
        {
            S[b^1] +=(1<<step) * d;
            D[b^1] +=d;
            num_b+=(1<<step);
        }
        S[a>>1]+=num_a * d;
        S[b>>1]+=num_b * d;
        step++;

    }
    for(a>>=1;a>0;a>>=1)
    {
        S[a]+=(num_a + num_b)*d;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);

    for(M=1;M<n+2;M<<=1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",A+i);
    }
    build();
    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);

            printf("%lld
",getSum());
        }
        else
        {
            scanf("%d%d%d",&a,&b,&d);
            update();
        }
    }
    return 0;
}

4. ZKW 트리 배열, 유도 공식: (추천)
두 개의 보조수 그룹이 필요합니다. B[i]는 A[1.i]가 지금까지 모두 얼마나 추가되었는지, C[i]는 A[1.i]가 지금까지 모두 얼마나 추가되었는지를 나타냅니다(또는 C[i]=B[i]*i).ADD(x,c)의 경우 B[x]에 c를 더하고 C[x]에 c*x를 더하면 된다(C[x]와 B[x] 간의 관계에 따라 얻을 수 있다).한편, ADD(x,c) 조작은 이렇게 A[1.i]의 합에 영향을 미친다. 만약에 x=i) A[1.i]의 합을 i*c로 한다.즉, A[1.i]의 합=B[i.N]의 합*i+C[1.i-1]의 합이다.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
#define N 100009
#define LL long long

LL B[N];
LL C[N];

int n,q,a,b,d;
int temp;
char c;
LL sum_a,sum_b;

int lowbit(int x)
{
    return x&(-x);
}
void updateB(int x,int d)
{
    while(x>0)
    {
        B[x] += d;
        x -=lowbit(x);//x^=lowbit(x)
    }
}
void updateC(int x,int d)
{
    int t = x;
    while(x<=n)
    {
        C[x]+=(LL)t*d;
        x+=lowbit(x);
    }
}

LL getSumB(int x)
{
    LL sum = 0;
    while(x<=n)
    {
        sum+=B[x];
        x += lowbit(x);
    }
    return sum;
}

LL getSumC(int x)
{
    LL sum = 0;
    while(x>0)
    {
        sum+=C[x];
        x -= lowbit(x);//x^=lowbit(x)
    }
    return sum;
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        updateB(i,temp);
        updateC(i,temp);
        if(i>1)
        {
            updateB(i-1,-temp);
            updateC(i-1,-temp);
        }
    }

    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);
            sum_b = 0;
            sum_a = 0;
            a -=1;
            if(b>0)
            {
                sum_b = getSumB(b)*b + getSumC(b-1);
            }
            if(a>0)
            {
                sum_a = getSumB(a)*a + getSumC(a-1);
            }

            printf("%lld
",sum_b-sum_a);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&d);
            updateB(b,d);
            updateC(b,d);
            if(a>1)
            {
                updateB(a-1,-d);
                updateC(a-1,-d);
            }
        }
    }
    return 0;
}
5.해법 4와 유사하지만 B[i]와 C[i] 두 개의 수조는 모두 접미사와
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
#define N 100009
#define LL long long

LL B[N];
LL C[N];

int n,q,a,b,d;
int temp;
char c;
LL sum_a,sum_b;

int lowbit(int x)
{
    return x&(-x);
}
LL getSum(int x){
    LL s1 = 0;
    LL s2 = 0;
    LL t = n - x;
    while (x <= n)
    {
        s1 += B[x];
        s2 += C[x];
        x += lowbit(x);
    }
    return s1 * t - s2;
}

void update(int x, int d){
    LL t = (LL) (n - x - 1) * d;
    while (x>0)
    {
         B[x] += d;
         C[x] += t;
         x -= lowbit(x);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        update(i,temp);
        update(i-1,-temp);
    }

    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",getSum(a)-getSum(b+1));
        }
        else
        {
            scanf("%d%d%d",&a,&b,&d);
            update(b,d);
            update(a-1,-d);
        }
    }
    return 0;
}

6.B[i]와 C[i]는 모두 접두사와
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
#define N 100009
#define LL long long

LL B[N];
LL C[N];

int n,q,a,b,d;
int temp;
char c;
LL sum_a,sum_b;

int lowbit(int x)
{
    return x&(-x);
}
LL getSum(int x){
    LL s1 = 0;
    LL s2 = 0;
    LL t = x;
    while (x)
    {
        s1 += B[x];
        s2 += C[x];
        x -= lowbit(x);
    }
    return s1 * t - s2;
}

void update(int x, int d){
    LL t = (LL) (x - 1) * d;
    while (x <= n)
    {
        B[x] += d;
        C[x] += t;
        x += lowbit(x);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        update(i,temp);
        update(i+1,-temp);
    }

    for(int i=0;i<q;i++)
    {
        scanf(" %c",&c);
        if(c == 'Q')
        {
            scanf("%d%d",&a,&b);
            printf("%lld
",getSum(b)-getSum(a-1));
        }
        else
        {
            scanf("%d%d%d",&a,&b,&d);
            update(a,d);
            update(b+1,-d);
        }
    }
    return 0;
}
7.트리 그룹 해법, 유도 과정:
우선, 업데이트 작업 업데이트(s, t, d)를 보고 구간 A[s]를...A[t]는 모두 d를 증가합니다. 우리는 하나의 수조delta[i]를 도입하여
A[i]...A[n]의 공통 증량, n은 배열의 크기입니다.그러면 업데이트 작업은 다음과 같이 변경될 수 있습니다.
1)delta[s]=delta[s]+d로 하여금 A[s]를...A[n] 동시에 d를 증가하지만, 이렇게 하면 A[t+1]...A[n]에 d를 더 넣었기 때문에
2) 델타[t+1] = 델타[t+1] - d, A[t+1]...A[n] 동시에 d 빼기
 
나중에 조회 조작query(s,t)를 보고 A[s]를 구하는데...A[t]의 구간과 접두사 합을 구하는 것으로 전환되고sum[i]=A[1]+...+A[i],
                            A[s]+...+A[t] = sum[t] - sum[s-1],
그러면 접두사와sum[x]는 어떻게 구하나요?그것은 두 부분으로 구성되어 있는데, 하나는 수조의 원시화이고, 다른 하나는 이 구간 내의 누적 증량화이며, 수조 A의 원시를
값은 그룹 org에 저장되고,델타[i]가sum[x]에 기여한 값이델타[i]*(x+1-i)이면
                            sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1
                                         = org[1]+...+org[x] + segma(delta[i]*(x+1-i))
                                         = segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i),1 <= i <= x
이것은 사실 세 개의 수조 org[i],delta[i]와delta[i]*i의 접두사와, org[i]의 접두사와 변하지 않는 것을 사전에 구할 수 있다.
delta[i]*i의 접두사와 끊임없이 변화하는 것은 두 개의 트리 그룹으로 유지할 수 있습니다.
#include <stdio.h>

#define N 100002

#define lowbit(i) ( i & (-i) )

/*  delta[i] [i,n]  */
long long c1[N];	/*  delta[i]  */
long long c2[N];	/*  delta[i]*i  */
long long sum[N];
int 	  A[N];
int n;

long long query(long long *array, int i)
{
	long long tmp;

	tmp = 0;
	while (i > 0) {
		tmp += array[i];
		i -= lowbit(i);
	}
	return tmp;
}

void update(long long *array, int i, long long d)
{
	while (i <= n) {
		array[i] += d;
		i += lowbit(i);
	}
}

int main()
{
	int 		q, i, s, t, d;
	long long 	ans;
	char		action;

    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif

	scanf("%d %d", &n, &q);
	for (i = 1; i <= n; i++) {
		scanf("%d", A+i);
	}
	for (i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + A[i];
	}

	while (q--) {
		getchar();
		scanf("%c %d %d", &action, &s, &t);
		if (action == 'Q') {
			ans = sum[t] - sum[s-1];
			ans += (t+1)*query(c1, t) - query(c2, t);
			ans -= (s*query(c1, s-1) - query(c2, s-1));
			printf("%lld
", ans);
		}
		else {
			scanf("%d", &d);
			/*  delta[i](s<=i<=t) d， 
			 * [s,n] d， [t+1,n] d
			 */
			update(c1, s, d);
			update(c1, t+1, -d);
			update(c2, s, d*s);
			update(c2, t+1, -d*(t+1));
		}
	}
	return 0;
}

8. 7 해법과 유사:
사실상 s와 t의 접두사와 접두사를 구하지 않고 [s,t]의 구간과 를 직접 구할 수 있다. 이것은 다음과 같다.
                                        sum[t] = segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)  1 <= i <= t
                                        sum[s-1] = segma(org[i]) + s*segma(delta[i]) - segma(delta[i]*i)  1 <= i <= s-1
[s, t]의 구간 및 표현:
sum[t]-sum[s-1] = org[s] + ... + org[t] + (t+1)*(delta[s] + ... + delta[t]) + (t-s+1)*(delta[1] + ... + delta[s-1])
                                - (delta[s]*s + ... + delta[t]*t)
                            = segma(org[i]) +(t+1)* segma(delta[i]) - segma(delta[i]*i) , s <= i <= t
                             + (t-s+1)*segma(delta[i]), 1 <= i <= s-1
문제는 세 개의 수조 org,delta[i]와delta[i]*i의 구간과 구하는 것으로 바뀌었고 라인 트리는 구간과 구하는 것을 직접 구할 수 있기 때문에 또 다른 것을 얻었다
#include <stdio.h>

#define N 100002

/*  delta[i] [i,n]  */
long long tree1[262144];	/*  delta[i]  */
long long tree2[262144];	/*  delta[i]*i  */
long long sum[N];
int		A[N];
int		n, M;

/*  [s,t]  */
long long query(long long *tree, int s, int t)
{
	long long tmp;

	tmp = 0;
	for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
		if (~s&1) {
			tmp += tree[s^1];
		}
		if (t&1) {
			tmp += tree[t^1];
		}
	}
	return tmp;
}

/*  i  */
void update(long long *tree, int i, long long d)
{
	for (i = (i+M); i > 0; i >>= 1) {
		tree[i] += d;
	}
}

int main()
{
	int 		q, i, s, t, d;
	long long 	ans;
	char		action;

    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif

	scanf("%d %d", &n, &q);
	for (i = 1; i <= n; i++) {
		scanf("%d", A+i);
	}
	for (i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + A[i];
	}

	for (M = 1; M < (n+2); M <<= 1);

	while (q--) {
		getchar();
		scanf("%c %d %d", &action, &s, &t);
		if (action == 'Q') {
			ans = sum[t] - sum[s-1];
			ans += (t+1)*query(tree1, s, t)+(t-s+1)*query(tree1, 1, s-1);
 			ans -= query(tree2, s, t);
			printf("%lld
", ans);
		}
		else {
			scanf("%d", &d);
			/*  delta[i](s<=i<=t) d， 
			 * [s,n] d， [t+1,n] d
			 */
			update(tree1, s, d);
			update(tree2, s, d*s);
			if (t < n) {
				update(tree1, t+1, -d);
				update(tree2, t+1, -d*(t+1));
			}
		}
	}
	return 0;
}

참고 자료:
http://kenby.iteye.com/blog/962159
http://www.shuizilong.com/house/archives/poj-3468-a-simple-problem-with-integers/
http://www.cnblogs.com/louisnit/archive/2012/2/29.html
Heroku에 배포하기 위한 React 애플리케이션 설정
[VRCHAT] 폭신한 스커트를 입고 앉아도 편안한 다이나믹 본 드레스.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage