P1975 國家集訓隊 排隊 樹套樹

2022-09-22 21:31:46 字數 1136 閱讀 6536

戳這裡

每次交換之後,\(n\log\) 的求逆序對,複雜度 \(o(mn\log)\)

我們發現每次交換 \(l\) 和 \(r\) 的時候,影響的區間只有 \([l,r]\)

具體來說 \(\delta = \sum_^ [a_i>a_l]+\sum_^ [a_i>a_r]-\sum_^[a_ia_r]\)

也就是是說我們需要一個資料結構支援,區間查詢一個區間內元素的個數,並單點修改

對於這種區間套區間的問題,我們可以用樹套樹解決

第一層的區間查詢可以用樹狀陣列來實現,第二層上動態開點值域線段樹

tip:

需要特判 \(l\) 和 \(r\) 兩個點的大小是否會帶來新的逆序對

#includeusing namespace std;

namespace zzc

while(isdigit(ch))

return x*f; }

const int maxn = 2e4+5;

int cnt,n,m,len,ans;

int a[maxn],root[maxn],b[maxn];

struct tree

t[maxn<<7];

int lowbit(int x)

int build()

void pushup(int rt)

void update(int &rt,int l,int r,int pos,int val)

int mid=(l+r)>>1;

if(pos<=mid) update(t[rt].lc,l,mid,pos,val);

else update(t[rt].rc,mid+1,r,pos,val);

pushup(rt); }

int query(int rt,int l,int r,int ql,int qr)

void tree_update(int rt,int pos,int val)

int tree_query(int l,int r,int ql,int qr)

void work() }

}int main()