區間查詢[2009國家集訓隊]小Z的襪子(hose)

PS:今天上午，非常郁悶，有很多簡單基礎的問題搞得我有些迷茫，哎，代碼幾天不寫就忘。目前又不當COO，還是得用心記代碼哦！

    轉載請注明出處，感謝 by---cxlove

恐怖的莫隊法算。。。覺感有了這個，是不是可以決解全部的區間查詢但是無修改的目題

許也不是最優的，但是O(n*sqrt(n))全完也是可以實驗的。

莫隊法算：對于兩個區間的查詢[l1,r1] ,[l2,r2]如果每加增一個區間元素或者删除，都能做到O(1)的話

那麼從[l1,r1]轉移到[l2,r2]，暴力可以做到|l1-l2|+|r1-r2|，就是manhattan距離

莫隊的論文始終沒有找到，是以隻是大緻的了解下，應該是證明出結構出哈密爾頓路徑是最優的。

但是可以用manhattan mst來結構，大約會是兩倍，然後莫隊證明出這樣轉移的限上是O(n*sqrt(n))。

是以對于這類無修改的區間查詢說來

可以先将全部的區間，當作維二平面上的點，求一次manhattan mst，然後根據mst來行進轉移

相鄰的兩個區間的查詢轉移，暴力決解。

​​Manhattan MST​​ 這裡有

    每日一道理

時間好比一條小溪，它能招引我們奔向生活的海洋；時間如同一葉扁舟，它将幫助我們駛向理想的彼岸；時間猶如一支畫筆，它會指點我們描繪人生的畫卷。

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <vector>
#include <cstring>
#define lowbit(x) (x&(-x)) 
#define LL long long 
using namespace std;  
const int N = 50005;  
struct Point{  
    int x,y,id;  
    bool operator<(const Point p)const{  
        return x!=p.x?x<p.x:y<p.y;  
    }  
}p[N],pp[N];  
//數狀數組，找(y-x)大于以後的，但是y+x最小的
struct BIT{  
    int min_val,pos;  
    void init(){  
        min_val=(1<<30);  
        pos=-1;  
    }  
}bit[N];  
//全部效有邊，Kruskal
struct Edge{  
    int u,v,d;  
    bool operator<(const Edge e)const{  
        return d<e.d;  
    }  
}e[N<<2];  
//前向星
struct Graph{
    int v,next;
}edge[N<<1];
int n,m,tot,pre[N];  
int total,start[N];
int find(int x){  
    return pre[x]=(x==pre[x]?x:find(pre[x]));  
}  
inline int dist(int i,int j){  
    return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);  
}  
inline void addedge(int u,int v,int d){  
    e[tot].u=u;  
    e[tot].v=v;  
    e[tot++].d=d;  
}  
inline void _add(int u,int v){
    edge[total].v=v;
    edge[total].next=start[u];
    start[u]=total++;
}
inline void update(int x,int val,int pos){  
    for(int i=x;i>=1;i-=lowbit(i))  
        if(val<bit[i].min_val)  
            bit[i].min_val=val,bit[i].pos=pos;  
}  
inline int ask(int x,int m){  
    int min_val=(1<<30),pos=-1;  
    for(int i=x;i<=m;i+=lowbit(i))  
        if(bit[i].min_val<min_val)  
            min_val=bit[i].min_val,pos=bit[i].pos;  
    return pos;  
}  
inline void Manhattan_minimum_spanning_tree(int n,Point *p){  
    int a[N],b[N];  
    for(int dir=0;dir<4;dir++){  
        //4種坐标換變  
        if(dir==1||dir==3){  
            for(int i=0;i<n;i++)  
                swap(p[i].x,p[i].y);  
        }  
        else if(dir==2){  
            for(int i=0;i<n;i++){  
                p[i].x=-p[i].x;  
            }  
        }  
        sort(p,p+n);  
        for(int i=0;i<n;i++){  
            a[i]=b[i]=p[i].y-p[i].x;  
        }  
        sort(b,b+n);  
        int m=unique(b,b+n)-b;  
        for(int i=1;i<=m;i++)  
            bit[i].init();  
        for(int i=n-1;i>=0;i--){  
            int pos=lower_bound(b,b+m,a[i])-b+1;   //BIT中從1開始  
            int ans=ask(pos,m);  
            if(ans!=-1)  
                addedge(p[i].id,p[ans].id,dist(i,ans));  
            update(pos,p[i].x+p[i].y,i);  
        }  
    }  
    sort(e,e+tot);  
    for(int i=0;i<n;i++)  
        pre[i]=i;  
    for(int i=0;i<tot;i++){  
        int u=e[i].u,v=e[i].v;  
        int fa=find(u),fb=find(v);  
        if(fa!=fb){ 
            pre[fa]=fb;  
            _add(u,v);
            _add(v,u);
        }  
    }  
}  
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}
LL up[N],down[N];
LL ans;
int col[N],vis[N]={0};
int cnt[N]={0};   //記載每種色顔湧現的次數
inline void add(int l,int r){
    for(int i=l;i<=r;i++){
        int c=col[i];
        ans-=(LL)cnt[c]*(cnt[c]-1)/2;
        cnt[c]++;
        ans+=(LL)cnt[c]*(cnt[c]-1)/2;
    }
}
inline void del(int l,int r){
    for(int i=l;i<=r;i++){
        int c=col[i];
        ans-=(LL)cnt[c]*(cnt[c]-1)/2;
        cnt[c]--;
        ans+=(LL)cnt[c]*(cnt[c]-1)/2;
    }
}
//[l1,r1]前一個區間 [l2,r2]以後區間
void dfs(int l1,int r1,int l2,int r2,int idx,int pre){  

    if(l2<l1) add(l2,l1-1);
    if(r2>r1) add(r1+1,r2);
    if(l2>l1) del(l1,l2-1);
    if(r2<r1) del(r2+1,r1);
    up[pp[idx].id]=ans;
    vis[idx]=1;
    for(int i=start[idx];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v]) continue;
        dfs(l2,r2,pp[v].x,pp[v].y,v,idx);
    }
    if(l2<l1) del(l2,l1-1);
    if(r2>r1) del(r1+1,r2);
    if(l2>l1) add(l1,l2-1);
    if(r2<r1) add(r2+1,r1);
}
int main(){  
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);  
    tot=total=0;
    memset(start,-1,sizeof(start));  
    for(int i=1;i<=n;i++)
        scanf("%d",&col[i]);
    for(int i=0;i<m;i++){  
        scanf("%d%d",&p[i].x,&p[i].y);  
        down[i]=(LL)(p[i].y-p[i].x+1)*(p[i].y-p[i].x)/2;
        p[i].id=i;  
        pp[i]=p[i];   //本副一份，便于面後DFS，或者之後按id序排
    } 
    Manhattan_minimum_spanning_tree(m,p);
    for(int i=0;i<m;i++){
        p[i].y=-p[i].y;
    }
    dfs(2,1,pp[0].x,pp[0].y,0,-1);
    for(int i=0;i<m;i++){
        LL g=gcd(up[i],down[i]);
        printf("%lld/%lld\n",up[i]/g,down[i]/g);
    }
    return 0;  
}      

文章結束給大家分享下程式員的一些笑話語錄： 　一邊用着越獄的ip，一邊拜喬幫主的果粉自以為是果粉，其實在喬幫主的眼裡是不折不扣的叛徒。