The overall dichotomy is good meow ~ looks like the monotonous divide and conquer optimization of decision-making. It can help you easily find the k-th decimal 2333333 (FOG) without writing various tree sets
Firstly, determine a decision interval. solve(l, r, L, R) represents the weight of the number of operations numbered in L ~ r and the answer to the query. In L ~ r, divide the answer in two each time, and divide the modification operation in L ~ r into left and right sides according to the weight < = mid and > mid of the modified number. If < = mid, put its subscript position in bit + 1, Divide the query operation in L ~ r into left and right sides according to sum > = k and < k in the query interval on bit. If < k, k should subtract sum in the query interval on bit, and then divide and treat according to the operation thrown to the left and right sides.
It should not be difficult to understand. Although the original order is modified by dividing the operation and inquiry into the left and right sides, the operations that will affect each other must be carried out in the original order, because the large number of modified ranking has no effect on the small number. First deal with the small number of answers, so when dealing with the large answer, k has subtracted the contribution of the small number of answers, Therefore, when dealing with the interval with large answer, it is not affected by the interval with small answer. In this way, we can achieve one O(N), a total of log(N) layers, plus bit complexity log(N), and total complexity O(Nlog^2N).
Specific process of overall dichotomy:
void solve(int l, int r, int L, int R)
{
if(l>r || L>R) return;
if(l==r)
{
for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l; //If Q [i] Ty = = 1 is a question, throw the answer in
return;
}
int mid=(l+r)>>1, cnt1=0, cnt2=0; //Two point answer
for(int i=L;i<=R;i++)
if(q[i].ty)
{
int tmp=query(q[i].y)-query(q[i].x-1); //sum of query interval on bit
if(tmp>=q[i].k) q1[++cnt1]=q[i]; //< = K on the left
else q[i].k-=tmp, q2[++cnt2]=q[i]; //>k is updated and lost to the right
}
else
{
if(q[i].x<=mid) add(q[i].pos, q[i].y), q1[++cnt1]=q[i]; //If the modified number < = mid, update the bit and throw it to the left
else q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y); //If it is modified, delete the value on bit
for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i]; //Throw it to the left~
for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i]; //Throw it to the right~
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R); //Divide and conquer~
}View Code
Example time~
Example 1 POJ2104 K-th Number
It's a naked k-th smallest interval Large template
This code is by Java Architect must see network-Structure Sorting
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
int n, m, x, y, k, cnt, cnt1, cnt2;
int tree[maxn], ans[maxn], a[maxn];
inline void read(int &k)
{
int f=1; k=0; char c=getchar();
while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
k*=f;
}
inline void add(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x) {int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
void solve(int l, int r, int L, int R)
{
if(l>r || L>R) return;
if(l==r)
{
for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l;
return;
}
int mid=(l+r)>>1, cnt1=0, cnt2=0;
for(int i=L;i<=R;i++)
if(q[i].ty)
{
int tmp=query(q[i].y)-query(q[i].x-1);
if(tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if(q[i].x<=mid) q1[++cnt1]=q[i], add(q[i].pos, q[i].y);
else q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y);
for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
read(n); read(m);
for(int i=1;i<=n;i++) read(x), q[++cnt]=(poi){x, 1, 0, i, 0};
for(int i=1;i<=m;i++) read(x), read(y), read(k), q[++cnt]=(poi){x, y, k, i, 1};
solve(-inf, inf, 1, cnt);
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
}View Code
Example 2 bzoj1901: Zju2112 Dynamic Rankings
With one more modification, the constant is superior to the BIT chairman tree, and the complexity is the same. It runs fast~
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
int n, m, x, y, k, cnt, cnt1, cnt2, tot;
int tree[maxn], ans[maxn], a[maxn];
char s[2];
inline void read(int &k)
{
int f=1; k=0; char c=getchar();
while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
k*=f;
}
inline void add(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x) {int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
void solve(int l, int r, int L, int R)
{
if(l>r || L>R) return;
if(l==r)
{
for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l;
return;
}
int mid=(l+r)>>1, cnt1=0, cnt2=0;
for(int i=L;i<=R;i++)
if(q[i].ty)
{
int tmp=query(q[i].y)-query(q[i].x-1);
if(tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if(q[i].x<=mid) add(q[i].pos, q[i].y), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y);
for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
read(n); read(m);
for(int i=1;i<=n;i++) read(a[i]), q[++cnt]=(poi){a[i], 1, 0, i, 0};
for(int i=1;i<=m;i++)
{
scanf("%s", s+1);
if(s[1]=='Q') read(x), read(y), read(k), q[++cnt]=(poi){x, y, k, ++tot, 1};
else read(x), read(y), q[++cnt]=(poi){a[x], -1, 0, x, 0}, q[++cnt]=(poi){a[x]=y, 1, 0, x, 0};
}
solve(-inf, inf, 1, cnt);
for(int i=1;i<=tot;i++) printf("%d\n", ans[i]);
}View Code
Example 3 bzoj3110: [Zjoi2013]K large number query
If you want to insert the number of an interval this time, if the inserted number < = mid, you can use the segment tree to add all + 1 to that interval
The k-th is n-c+1, the k-th is small, and finally output n-ans+1
This code is by Java Architect must see network-Structure Sorting
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=50010, inf=2147483647;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
struct tjm{int sum, delta;}tree[maxn<<2];
int n, m, ty, x, y, z, cnt, cnt1, cnt2, tot, N;
int ans[maxn];
inline void read(int &k)
{
int f=1; k=0; char c=getchar();
while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
k*=f;
}
inline void up(int x){tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;}
inline void down(int x, int l, int r)
{
int mid=(l+r)>>1;
tree[x<<1].delta+=tree[x].delta; tree[x<<1|1].delta+=tree[x].delta;
tree[x<<1].sum+=tree[x].delta*(mid-l+1); tree[x<<1|1].sum+=tree[x].delta*(r-mid);
tree[x].delta=0;
}
void update(int x, int l, int r, int cl, int cr, int delta)
{
if(cl<=l && r<=cr) {tree[x].delta+=delta; tree[x].sum+=delta*(r-l+1); return;}
down(x, l, r);
int mid=(l+r)>>1;
if(cl<=mid) update(x<<1, l, mid, cl, cr, delta);
if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta);
up(x);
}
int query(int x, int l, int r, int cl, int cr)
{
if(cl<=l && r<=cr) return tree[x].sum;
down(x, l, r);
int mid=(l+r)>>1, ans=0;
if(cl<=mid) ans=query(x<<1, l, mid, cl, cr);
if(cr>mid) ans+=query(x<<1|1, mid+1, r, cl, cr);
return ans;
}
void solve(int l, int r, int L, int R)
{
if(l>r || L>R) return;
if(l==r)
{
for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=n-l+1;
return;
}
int mid=(l+r)>>1, cnt1=0, cnt2=0;
for(int i=L;i<=R;i++)
if(q[i].ty)
{
int tmp=query(1, 1, n, q[i].x, q[i].y);
if(tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if(q[i].k<=mid) update(1, 1, n, q[i].x, q[i].y, 1), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) if(!q1[i].ty) update(1, 1, n, q1[i].x, q1[i].y, -1);
for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
#undef int
int main()
{
read(n); read(m);
for(int i=1;i<=m;i++)
{
read(ty); read(x); read(y); read(z);
if(ty==1) q[i]=(poi){x, y, n-z+1, i, 0};
else q[i]=(poi){x, y, z, ++tot, 1};
}
solve(1, n, 1, m);
for(int i=1;i<=tot;i++) printf("%lld\n", ans[i]);
}View Code
Example 4 bzoj2738: matrix multiplication
Just change example 1 into a two-dimensional tree array
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x1, yy1, x2, y2, k, pos;}q[maxn], q1[maxn], q2[maxn];
int n, m, x1, yy1, x2, y2, cnt, x, k, mx;
int tree[510][510], ans[maxn];
inline void read(int &k)
{
int f=1; k=0; char c=getchar();
while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
k*=f;
}
inline void add2(int x, int y, int delta) {for(;y<=n;y+=y&-y) tree[x][y]+=delta;}
inline void add1(int x, int y, int delta) {for(;x<=n;x+=x&-x) add2(x, y, delta);}
inline int query2(int x, int y) {int sum=0; for(;y;y-=y&-y) sum+=tree[x][y]; return sum;}
inline int query1(int x, int y) {int sum=0; for(;x;x-=x&-x) sum+=query2(x, y); return sum;}
inline int query(int x1, int yy1, int x2, int y2)
{return query1(x2, y2)-query1(x1-1, y2)-query1(x2, yy1-1)+query1(x1-1, yy1-1);}
void solve(int l, int r, int L, int R)
{
if(l>r || L>R) return;
if(l==r)
{
for(int i=L;i<=R;i++) if(q[i].pos) ans[q[i].pos]=l;
return;
}
int mid=(l+r)>>1, cnt1=0, cnt2=0;
for(int i=L;i<=R;i++)
if(q[i].pos)
{
int tmp=query(q[i].x1, q[i].yy1, q[i].x2, q[i].y2);
if(tmp>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=tmp, q2[++cnt2]=q[i];
}
else
{
if(q[i].k<=mid) add1(q[i].x1, q[i].yy1, 1), q1[++cnt1]=q[i];
else q2[++cnt2]=q[i];
}
for(int i=1;i<=cnt1;i++) if(!q1[i].pos) add1(q1[i].x1, q1[i].yy1, -1);
for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
inline int max(int a, int b){return a>b?a:b;}
int main()
{
read(n); read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) read(x), q[++cnt]=(poi){i, j, 0, 0, x, 0}, mx=max(mx, x);
for(int i=1;i<=m;i++)
{
read(x1); read(yy1); read(x2); read(y2); read(k);
q[++cnt]=(poi){x1, yy1, x2, y2, k, i};
}
solve(0, mx+1, 1, cnt);
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
}View Code
Continuous updating~
Information: http://blog.csdn.net/lwt36/article/details/50669972