网站建设工资一月多少,辽宁省工程造价信息网,关于门户网站建设情况通报,做微信用什么网站解析
写了不少线段树上二分#xff0c;原来树状数组上也是可以二分的
首先如果aiia_iiaii#xff0c;那必然无法删除#xff0c;下面只考虑aiia_iiaii的情况 本题试图离线不难想到#xff0c;但我一开始总是按照刻板思维尝试按序移动左端点原来树状数组上也是可以二分的
首先如果aiia_iiaii那必然无法删除下面只考虑aiia_iiaii的情况 本题试图离线不难想到但我一开始总是按照刻板思维尝试按序移动左端点结果根本没法做… 反过来想移动右端点就可做多了 设fif_ifi表示当前右端点为r的情况下[i,r]最多可以删掉的数量 那么我们当把r移动到r1时只有fii−aif_ii-a_ifii−ai时才会对fif_ifi产生1的贡献 不难发现这个f是单调不升的所以符合上面那个条件的f应该是一段前缀可以利用二分求出 然后就是简单的对f区间1用树状数组维护即可
#includebits/stdc.h
using namespace std;
const int N3e5100;
const int mod1e97;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}int n,m;int f[N],a[N],mi[20];
inline void add(int p,int v){for(;pn;pp-p) f[p]v;return;
}
inline int ask(int p){int res(0);for(;p;p-p-p) resf[p];return res;
}
inline int find(int val){int res0,pl0;for(int k18;k0;k--){if(plmi[k]n||resf[plmi[k]]val) continue;plmi[k];resf[pl];}return pl;
}
struct query{int l,r,id;bool operator (const query oth)const{return roth.r;}
}p[N];
int ans[N];
int main(){#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);#endifmi[0]1;for(int i1;i18;i) mi[i]mi[i-1]1;nread();mread();for(int i1;in;i) a[i]i-read();for(int i1;im;i) p[i](query){(int)read()1,n-(int)read(),i};sort(p1,p1m);int pl1;//for(int i1;in;i) printf(%d ,a[i]);//putchar(\n);for(int i1;in;i){if(a[i]0){int plfind(a[i]);//printf(i%d pl%d\n,i,pl);add(1,1);add(min(pl1,i1),-1);}while(plmp[pl].ri){ans[p[pl].id]ask(p[pl].l);pl;}}for(int i1;im;i) printf(%d\n,ans[i]);return 0;
}
/*
2 3
7 4 9 9
1 2 8
3 1
4 2 4
*/
