HDU 4638 Group(모 팀 알고리즘 | | 세그먼트 트리 분리 쿼리)

제목 주소: HDU 4638이 먼저 모팀을 썼습니다. 모팀은 물을 건너갈 수 있습니다.간단해, 더 이상 말하지 마.코드는 다음과 같습니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
int a[MAXN];
LL ha[MAXN], ans[MAXN], res;
struct node {
        int l, r, id, pos;
} fei[MAXN];
bool cmp(node x, node y)
{
        return x.posvoid reduce(int tmp)
{
        if(ha[tmp-1]&&ha[tmp+1]) res++;
        else if(!ha[tmp-1]&&!ha[tmp+1]) res--;
        ha[tmp]=0;
}
void add(int tmp)
{
        if(ha[tmp-1]&&ha[tmp+1]) res--;
        else if(!ha[tmp-1]&&!ha[tmp+1]) res++;
        ha[tmp]=1;
}
int main()
{
        int t, n, m, i, j, k, tmp, l, r;
        scanf("%d",&t);
        while(t--) {
                scanf("%d%d",&n,&m);
                for(i=1; i<=n; i++) {
                        scanf("%d",&a[i]);
                }
                k=sqrt(n*1.0);
                for(i=0; iscanf("%d%d",&fei[i].l,&fei[i].r);
                        fei[i].id=i;
                        fei[i].pos=fei[i].l/k;
                }
                sort(fei,fei+m,cmp);
                memset(ha,0,sizeof(ha));
                l=1;
                r=0;
                res=0;
                for(i=0; iwhile(r>fei[i].r) {
                                tmp=a[r];
                                reduce(tmp);
                                r--;
                        }
                        while(rwhile(lwhile(l>fei[i].l) {
                                l--;
                                tmp=a[l];
                                add(tmp);
                        }
                        ans[fei[i].id]=res;
                }
                for(i=0; iprintf("%I64d
",ans[i]);
                }
        }
        return 0;
}

그리고 문제 보고서를 보니 라인 트리+오프라인 조회도 가능하다.그리고 신기한 방법..우선 오프라인으로 저장해 두세요.그리고 왼쪽에서 오른쪽으로 유지보수를 하는데 유지보수는 앞의 값이 현재 매거 값에 대한 상대적인 개수입니다.현재 i개수에 대해 말하자면 먼저 이 수의 값을 1로 갱신하여 하나의 독립된 열을 대표한 다음에 a[i]-1과 a[i]+1 앞에 존재하는지 존재하지 않는다. 만약에 존재한다면 앞의 두 수는 이미 독립된 직렬로 할 수 없다는 것을 의미한다. a[i]에 비해 a[i]의 직렬에 공존할 수 있기 때문에 a[i]-1과 a[i]+1을 각각 -1.그리고 r값이 i인 질문에서 직접 라인 트리를 구하면 됩니다.코드는 다음과 같습니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
#define root 1, n, 1
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
int a[MAXN], pos[MAXN], sum[MAXN<<2], ans[MAXN];
struct node
{
        int l, r, id;
}fei[MAXN];
bool cmp(node x, node y)
{
        return x.rvoid PushUp(int rt)
{
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void Update(int p, int x, int l, int r, int rt)
{
        if(l==r){
                sum[rt]+=x;
                return ;
        }
        int mid=l+r>>1;
        if(p<=mid) Update(p,x,lson);
        else Update(p,x,rson);
        PushUp(rt);
}
int Query(int ll, int rr, int l, int r, int rt)
{
        if(ll<=l&&rr>=r){
                return sum[rt];
        }
        int mid=l+r>>1, ans=0;
        if(ll<=mid) ans+=Query(ll,rr,lson);
        if(rr>mid) ans+=Query(ll,rr,rson);
        return ans;
}
int main()
{
        int t, n, m, i, j;
        scanf("%d",&t);
        while(t--){
                scanf("%d%d",&n,&m);
                for(i=1;i<=n;i++){
                        scanf("%d",&a[i]);
                        pos[a[i]]=i;
                }
                for(i=0;iscanf("%d%d",&fei[i].l,&fei[i].r);
                        fei[i].id=i;
                }
                memset(sum,0,sizeof(sum));
                sort(fei,fei+m,cmp);
                j=0;
                for(i=1;i<=n;i++){
                        Update(i,1,root);
                        if(a[i]>1&&pos[a[i]-1]1],-1,root);
                        if(a[i]1]1],-1,root);
                        while(jfor(i=0;iprintf("%d
",ans[i]);
                }
        }
        return 0;
}