전체 2점에서 CDQ로 나누기

54703 단어

전체 2점에서 CDQ로 나누기


1.전체2점

  • 전체 2점은 하나의 양(일반적으로 답안)을 2점으로 나누고 만족한 부분에 대해mid로 나누어 왼쪽 부분으로 나누어 2점을 주고 왼쪽 경계가 오른쪽 경계와 같을 때까지 만족하지 않으면 이미 얻은 부분을 잘라내고mid로 나누어 오른쪽 부분으로 나누어 귀속을 실현한다.
  • 와 cdqcdq분치의 가장 큰 차이점은 일반적으로 전체 2분은 먼저 처리하고 영향을 주고 아래로 옮기는 것이고 cdqcdq분치는 먼저 처리하고 다시 처리하는 영향이다.
  • 템플릿 bzo j bzoj bzoj 2527
    #include
#include
#include
#include
#include
#define mid ((nl+nr)>>1)
#define maxn 300005
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//  
int n,m,k;
int res[maxn];
int id[maxn],temp[maxn];
int bel[maxn],ned[maxn];
int z[maxn],y[maxn],t[maxn];
vector<int>edge[maxn];
//  
ll dat[maxn];
int lowbit(int now)
{
    return (now&(-now));
}
void update(int now,int add)
{
    for(int i=now;i<=m;i+=lowbit(i))
    {
        dat[i]+=add;
    }
}
ll query(ll pos)
{
    ll ans=0;
    for(int i=pos;i>=1;i-=lowbit(i))
    {
        ans+=dat[i];
    }
    return ans;
}
void insert(int now,int op)
{
    if(z[now]<=y[now])
    {
        update(z[now],op*t[now]);
        update(y[now]+1,-op*t[now]);
    }
    else
    {
        update(z[now],op*t[now]);
        update(1,op*t[now]);
        update(y[now]+1,-op*t[now]);
    }
}
ll sum[maxn];
//dfs( ， )
void dfs(int ql,int qr,int nl,int nr)
{
    if(ql>qr) return;
    if(nl==nr)
    {
        for(int i=ql;i<=qr;i++)
        {
            res[id[i]]=nl;
        }
        return;
    }
     
    for(int i=nl;i<=mid;i++)
    {
        insert(i,1);
    }
     
    for(int i=ql;i<=qr;i++)// ql qr， ， 。 
    {
        sum[id[i]]=0;
    }
     
    for(int i=ql;i<=qr;i++)
    {
        int len1=edge[id[i]].size();
        for(int j=0;j<len1;j++)
        {
            sum[id[i]]+=query(edge[id[i]][j]);
            if(sum[id[i]]>=ned[id[i]]) break;
        }
    }
    int cnt=0;
    for(int i=ql;i<=qr;i++)// ， ，  
    {
        if(sum[id[i]]>=ned[id[i]])
        cnt++;
    }
    int l1=ql,l2=ql+cnt;
    for(int i=ql;i<=qr;i++)
    {
        if(sum[id[i]]>=ned[id[i]])
        {
            temp[l1++]=id[i];
        }
        else
        {
            temp[l2++]=id[i];
            ned[id[i]]-=sum[id[i]];//  
        }
    }
     
    for(int i=ql;i<=qr;i++)
    id[i]=temp[i];
     
    for(int i=nl;i<=mid;i++)
    {
        insert(i,-1);//  
    }
    dfs(ql,ql+cnt-1,nl,mid);
    dfs(ql+cnt,qr,mid+1,nr);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int x;
        x=read();
        edge[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        ned[i]=read();
        id[i]=i;
    }
    k=read();
    for(int i=1;i<=k;i++)
    {
        z[i]=read();
        y[i]=read();
        t[i]=read();
    }
     
    k++;
    z[k]=1;y[k]=m;t[k]=1000000009;
    dfs(1,n,1,k);
     
    for(int i=1;i<=n;i++)
    {
        if(res[i]!=k) printf("%d
    "    ,res[i]);
        else printf("NIE
    "    );
    }
}
  • 예제
  • bzojbzojbzojbzoj2527 입문문제, 매번 절반씩 내리는 유성우, 위치마다 충분하게 내리는지, 충분하게 왼쪽으로 돌아가는지, 오른쪽으로 돌아가는지 봅니다.
  • bzojbzojbzoj3110은 구간 가수의 k대수 조회가 있고 답안의 값에 대해 2분을 한다. 수정 작업은 함께 2분을 한다. 내부는 시간에 따라 정렬해야 한다. 수정 작업은 답안에 영향을 미치기 때문이다.
  • bzojbzojbzoj4009는 나무에 두 가지 경로를 정하고 두 번째 경로는 권한이 있으며 첫 번째 경로가 포함하는 두 번째 경로의 권한이 큰 k를 구한다.이것은 신선제라서 사고방식이 나는 널리 보급될 여지가 있다고 생각한다.첫 번째 경로를 점(dfn[x], dfn[y])(dfn[x], dfn[y])(dfn[x], dfn[y])로 보고 여기에 dfn[x]

    • 2. CDQ 분할 치료

  • CDQ 분치의 정수는 처음에 어떤 차원의 X에 따라 순서를 정하고 먼저 왼쪽의 것을 처리한 다음에 오른쪽의 것을 처리한다. 순서가 돌아온 후에 먼저 앞줄의 순서의 성질이 있다. 즉, 왼쪽의 X는 오른쪽의 X보다 작고 왼쪽의 모든 원소는 다른 차원의 Y에 따라 순서를 정한다.이렇게 귀착된 후에 이런 순서의 성질에 의존하여 왼쪽이 오른쪽에 미치는 영향을 처리하고 Y에 대한 순서를 다시 거슬러 올라간다.
  • CDQ는 일반적으로 2, 3차원 편차 문제를 구한다.
  • 코드 bzo j bzoj bzoj 3262 길에 꽃이 피었음
    • #include
#include
#include
#include
#define maxn 200005
#define mid ((l+r)>>1)
using namespace std;
struct nod
{
    int x,y,z,id;
    nod()
    {
        x=0;
        y=0;
        z=0;
        id=0;
    }
}a[maxn],b[maxn];
int n,k;
int dat[maxn];
int ans[maxn];
bool operator<(nod a,nod b)
{
    return a.x!=b.x ? a.x<b.x : (a.y!=b.y ? a.y<b.y : a.z<b.z);
}
bool operator==(nod a,nod b)
{
    return a.x==b.x && a.y==b.y && a.z==b.z;
}
int lowbit(int now)
{
    return (now&(-now));
}
void add(int x,int val)
{
    for(int i=x;i<=k;i+=lowbit(i))
        dat[i]+=val;
}
int query(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=dat[i];
    return ans;
}
void cdq(int l,int r)
{
    if(l>=r) return;
    cdq(l,mid);
    cdq(mid+1,r);
    int s1=l,s2=mid+1;
    while(s1<=mid || s2<=r)
    {
        if(s2>r || (s1<=mid && a[s1].y<=a[s2].y))
        {
            add(a[s1].z,1);
            b[l+(s1-l)+(s2-(mid+1))]=a[s1];
            s1++;
        }
        else
        {
            ans[a[s2].id]+=query(a[s2].z);
            b[l+(s1-l)+(s2-(mid+1))]=a[s2];
            s2++;
        }
    }
    for(int i=l;i<=mid;i++)
    add(a[i].z,-1);
    for(int i=l;i<=r;i++)
    a[i]=b[i];
}
int cnt[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        a[i].id=i;
    }
    sort(a+1,a+1+n);
     
    for(int i=n;i>=1;i--)
    {
        if(a[i]==a[i+1])
            ans[a[i].id]=ans[a[i+1].id]+1;
        // ， ， 。
    }
     
    cdq(1,n);
    for(int i=1;i<=n;i++)
    cnt[ans[i]]++;
    for(int i=0;i<n;i++)
    printf("%d
    "    ,cnt[i]);  
}
  • bzo j bzoj bzoj 3262 길에 꽃이 피는 방법은 모두 앞에서 말했듯이 여기서 왼쪽이 오른쪽에 미치는 영향을 처리할 때 쌍지침의 사고방식을 이용하여 왼쪽의 s1s 를 먼저 이동한다.1s1 오른쪽 s2s 보증2s2에 대응하는 y는 왼쪽보다 크고 이어서 나무상수조를 통해 3차원을 통계한다.그러나 두 원소가 완전히 같다면 오른쪽에도 답안에 기여할 수 있으니 덧붙여야 한다.
    • 강철의 뱀신.
    C++ 프로그래머이지만 Intel RealSense SDK를 사용하여 웃음의 정도를 판정하고 싶습니다(준비편)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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