php网站开发范例,百度关键词优化多少钱一年,求职招聘网站开发代码,不用登录的小游戏网站遇事不决#xff0c;二分试试 解析
很好的一道题 真是把主席树玩明白了 一个关于中位数的常用trick#xff1a; 二分答案mid#xff0c;把mid的看成1#xff0c;mid的看成-1#xff0c;然后看最大子段和是否0 然而如果对离散化后的每一个值建一棵小白逛公园那… 遇事不决二分试试 解析
很好的一道题 真是把主席树玩明白了 一个关于中位数的常用trick 二分答案mid把mid的看成1mid的看成-1然后看最大子段和是否0 然而如果对离散化后的每一个值建一棵小白逛公园那样的线段树显然时空双炸 这里主席树就用上了 注意到关于相邻的值域所建的两棵主席树只有个别值从1变成-1 所以就用主席树优化时空即可 时间复杂度mlogn2mlogn^2mlogn2空间复杂度nlognnlognnlogn
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N20050;
inline 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 tot,r[N];
struct node{int sum,l,r;
};
struct tree{int ls,rs;node o;
}tr[N*20];
inline node merge(node a,node b){node res;res.suma.sumb.sum;res.lmax(a.l,a.sumb.l);res.rmax(b.r,b.suma.r);return res;
}
#define pushup(k) tr[k].omerge(tr[tr[k].ls].o,tr[tr[k].rs].o)
inline int copy(int x){tr[tot]tr[x];return tot;
}
#define mid ((lr)1)
void build(int k,int l,int r){kcopy(k);if(lr){tr[k].o(node){1,1,1};return;}build(tr[k].ls,l,mid);build(tr[k].rs,mid1,r);pushup(k);//printf(k%d (%d %d) sum%d l%d r%d\n,k,l,r,tr[k].o.sum,tr[k].o.l,tr[k].o.r);
}
void upd(int k,int l,int r,int p,int v){kcopy(k);if(lr){tr[k].o(node){v,max(v,0),max(v,0)};return;}if(pmid) upd(tr[k].ls,l,mid,p,v);else upd(tr[k].rs,mid1,r,p,v);pushup(k);return;
}
node ask(int k,int l,int r,int x,int y){//printf( k%d (%d %d) x%d y%d sum%d\n,k,l,r,x,y,tr[k].o.sum);if(xlry) return tr[k].o;else if(ymid) return ask(tr[k].ls,l,mid,x,y);else if(xmid) return ask(tr[k].rs,mid1,r,x,y);else return merge(ask(tr[k].ls,l,mid,x,y),ask(tr[k].rs,mid1,r,x,y));
}
int a[N],q[N],num;
vector intv[N];
int w[5];
bool check(int k,int a,int b,int c,int d){//printf(check:k%d x%d (%d %d) (%d %d)\n,k,q[k],a,b,c,d);node oask(r[k],1,n,b,c),uask(r[k],1,n,a,b-1),vask(r[k],1,n,c1,d);//printf(res%d%d%d\n\n,o.sum,u.r,v.l);return o.sumu.rv.l0;
}
int main(){nread();for(int i1;in;i) a[i]q[i]read();sort(q1,q1n);numunique(q1,q1n)-q-1;for(int i1;in;i){a[i]lower_bound(q1,q1num,a[i])-q;v[a[i]].push_back(i);}build(r[1],1,n);for(int i1;inum;i){r[i1]r[i];for(int j0;jv[i].size();j){int plv[i][j];upd(r[i1],1,n,pl,-1);}}mread();int lst0;for(int i1;im;i){for(int j1;j4;j) w[j](read()lst)%n;sort(w1,w14);int aw[1],bw[2],cw[3],dw[4];a;b;c;d;int st1,ednum;while(sted){int o(sted1)1;if(check(o,a,b,c,d)) sto;else edo-1;}printf(%d\n,lstq[st]);}return 0;
}
