[uoj228] 기초 데이터 구조 연습 문제 풀이 보고서

이 문제는 정말 대단하다.
문제를 다 읽어 보다.서로 인접한 두 개의 숫자가 근호를 열면 차이는 a-b에서 a−−b瀀로 변한다. 이것은 a瀀+b瀀를 제외하고는 곧 0이 될 것이다. 바보 같은 문제야!이렇게 하면 한 그루의 라인 트리만 만들 수 있다. 만약에 한 구간이 모두 하나의 숫자라면 직접 뿌리 번호를 따서 덮어쓰기 표시를 하는 것과 같다. 그렇지 않으면 귀속된다.이렇게 귀속되는 조건은 한 구간에 서로 인접한 두 개의 수차가 0이 되지 않는 것이다. 그러면 원 구간이 lg구간의 길이와 작은 구간으로 갈라질 수 있고 한 구간에 대해 말하자면 이런 상황만 초래할 수 있다.구간을 더하면 양쪽 끝의 차이를 리셋한 셈이기 때문에 시간 복잡도는 O(n+m)lgnlgn)이다.그리고 한 번 쓰고 70.데이터를 보니차이는 1... 침구?!원래 당차가 1일 때 근호를 다 열었을 때 차이가 있을 수도 있고 1이 될 수도 있다. 만약에 a가 완전한 제곱수라면 b=a-1, 그러면 ⌊a≠⌋=⌊b≠⌋+1이다.그러나 차이가 1이어야만 이런 상황이 나타날 수 있다. 만약에 a⌊a≠=⌊b≠+2라면 a-b의 가장 작은 상황도 a=9, b=3, a-b=6이기 때문이다.
이거 해킹 좀 세네.그래서 나는 원래 한 구간의 모든 수가 같을 때 통일적으로 처리한다고 생각했다. 그러면 바꾸어 모든 수차≤1로 바꾸면 통일적으로 처리하고 최대치, 최소치, 최대치의 출현 횟수를 기록한다.그리고 고쳐, 고쳐, 드디어ac야.
그리고 대신의 문제풀이를 경배했는데, 원래 1이 모자랄 때는 구간감조작으로 간주하면 된다!나 역시 바보야...코드:

#include
#include
using namespace std;
#include
#include
#include
const int N=1e5+5,M=1e5+5;
typedef long long LL;
int a[N];

char * cp=(char *)malloc(5000000);
void in(int &x){
    while(*cp<'0'||*cp>'9')++cp;
    for(x=0;*cp>='0'&&*cp<='9';)x=x*10+(*cp++^'0');
}

char * os=(char *)malloc(2000000),* op=os;
void out(LL x)
{
    if(x)
    {
        out(x/10);
        *op++=x%10^'0';
    }
}

struct SS
{
    LL sum;

    LL delta;

    LL max,min;
    int maxcnt;
    LL cover0,cover1;
}segt[N<<2];
#define lson node*2,l,(l+r)/2
#define rson node*2+1,(l+r)/2+1,r
#define self node,l,r
void out(int node,int l,int r){
    printf("Segt(%d,[%d,%d])={sum=%I64d,delta=%I64d,max=%I64d,min=%I64d,maxcnt=%d,cover0=%I64d,cover1=%I64d}
",node,l,r,segt[node].sum,segt[node].delta,segt[node].max,segt[node].min,segt[node].maxcnt,segt[node].cover0,segt[node].cover1);
}
void pushup(int node)
{
    segt[node].sum=segt[node<<1].sum+segt[node<<1|1].sum;
    segt[node].max=max(segt[node<<1].max,segt[node<<1|1].max);
    segt[node].min=min(segt[node<<1].min,segt[node<<1|1].min);

    segt[node].maxcnt=0;
    if(segt[node<<1].max==segt[node].max)segt[node].maxcnt+=segt[node<<1].maxcnt;
    if(segt[node<<1|1].max==segt[node].max)segt[node].maxcnt+=segt[node<<1|1].maxcnt;
}
void cover_paint(int node,int l,int r,LL cover0,LL cover1)
{
    //printf("cover_paint(%d,[%d,%d],%I64d,%I64d)
",node,l,r,cover0,cover1);

    segt[node].delta=0;
    segt[node].sum=cover0*segt[node].maxcnt+(r-l+1-segt[node].maxcnt)*cover1;
    segt[node].max=segt[node].cover0=cover0,segt[node].min=segt[node].cover1=cover1;
    if(cover0==cover1)segt[node].maxcnt=r-l+1;
}
void delta_paint(int node,int l,int r,LL delta)
{
    segt[node].sum+=(r-l+1)*delta;
    segt[node].max+=delta,segt[node].min+=delta;
    if(segt[node].cover0)segt[node].cover0+=delta,segt[node].cover1+=delta;
    else segt[node].delta+=delta;
}
void pushdown(int node,int l,int r)
{
    if(segt[node].cover0)
    {
        LL lcover=segt[node<<1].max>=segt[node<<1|1].max?segt[node].cover0:segt[node].cover1,rcover=segt[node<<1|1].max>=segt[node<<1].max?segt[node].cover0:segt[node].cover1;
        cover_paint(lson,lcover,segt[node<<1].max==segt[node<<1].min?lcover:segt[node].cover1);
        cover_paint(rson,rcover,segt[node<<1|1].max==segt[node<<1|1].min?rcover:segt[node].cover1);
        segt[node].cover0=0;
    }
    else if(segt[node].delta)
    {
        delta_paint(lson,segt[node].delta),delta_paint(rson,segt[node].delta);
        segt[node].delta=0;
    }
}
void build(int node,int l,int r)
{
    if(l==r)segt[node]=(SS){a[l],0,a[l],a[l],1};
    else
    {
        build(lson),build(rson);
        pushup(node);
    }

    //out(self);
}
void add(int node,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R)delta_paint(self,x);
    else
    {
        pushdown(self);
        if(L<=(l+r)/2)add(lson,L,R,x);
        if(R>(l+r)/2)add(rson,L,R,x);
        pushup(node);
    }

    //out(self);
}
void sqroot(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R&&segt[node].max-segt[node].min<=1)cover_paint(self,(LL)sqrt(segt[node].max),(LL)sqrt(segt[node].min));
    else
    {
        pushdown(self);
        if(L<=(l+r)/2)sqroot(lson,L,R);
        if(R>(l+r)/2)sqroot(rson,L,R);
        pushup(node);
    }

    //out(self);
}
LL query(int node,int l,int r,int L,int R){
    //out(self);

    if(L<=l&&r<=R)return segt[node].sum;
    else
    {
        pushdown(self);
        LL ans=0;
        if(L<=(l+r)/2)ans+=query(lson,L,R);
        if(R>(l+r)/2)ans+=query(rson,L,R);
        return ans;
    }
}
int main(){
    freopen("uoj228.in","r",stdin);
    freopen("uoj228.out","w",stdout);
    fread(cp,1,5000000,stdin);
    int n,m;
    in(n),in(m);
    for(int i=1;i<=n;++i)in(a[i]);
    build(1,1,n);
    int opt,l,r,x;
    while(m--){
        //puts("----------");

        in(opt),in(l),in(r);
        switch(opt){
            case 1:
                in(x);
                add(1,1,n,l,r,x);
                break;
            case 2:
                sqroot(1,1,n,l,r);
                break;
            case 3:
                out(query(1,1,n,l,r));
                *op++='
';
                break;
        }
    }
    fwrite(os,1,op-os,stdout);
}

요약: ① 아래의 정리와 아래의 정리는 차이가 있다.반드시 이 문제를 똑똑히 고려해야 한다.