免费网站代理访问,ppt制作软件免费模板,无锡网站seo外包,重庆铜梁网站建设题目链接 洛谷P4559 题解 只会做\(70\)分的\(O(nlog^2n)\) 如果本来就在区间内的人是不用动的#xff0c;区间右边的人往区间最右的那些空位跑#xff0c;区间左边的人往区间最左的那些空位跑 找到这些空位就用二分 主席树 理应可以在主席树上的区间二分而做到\(O(nlogn)\)区间右边的人往区间最右的那些空位跑区间左边的人往区间最左的那些空位跑 找到这些空位就用二分 主席树 理应可以在主席树上的区间二分而做到\(O(nlogn)\)但是写不出来先留着坑 #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#includemap
#define REP(i,n) for (register int i 1; i (n); i)
#define mp(a,b) make_pairint,long long int(a,b)
#define cp pairint,long long int
#define LL long long int
using namespace std;
const int maxn 500005,maxm 11000005,INF 1000000000;
inline int read(){int out 0,flag 1; char c getchar();while (c 48 || c 57){if (c -) flag -1; c getchar();}while (c 48 c 57){out (out 3) (out 1) c - 48; c getchar();}return out * flag;
}
int N,n,m,rt[maxn];
int ls[maxm],rs[maxm],num[maxm],cnt;
LL sum[maxm];
void modify(int u,int pre,int l,int r,int pos){u cnt;sum[u] sum[pre] pos; num[u] num[pre] 1;ls[u] ls[pre]; rs[u] rs[pre];if (l r) return;int mid l r 1;if (mid pos) modify(ls[u],ls[pre],l,mid,pos);else modify(rs[u],rs[pre],mid 1,r,pos);
}
int q_num(int u,int v,int l,int r,int L,int R){if (l L r R) return num[u] - num[v];int mid l r 1;if (mid R) return q_num(ls[u],ls[v],l,mid,L,R);if (mid L) return q_num(rs[u],rs[v],mid 1,r,L,R);return q_num(ls[u],ls[v],l,mid,L,R) q_num(rs[u],rs[v],mid 1,r,L,R);
}
LL q_sum(int u,int v,int l,int r,int L,int R){if (l L r R) return sum[u] - sum[v];int mid l r 1;if (mid R) return q_sum(ls[u],ls[v],l,mid,L,R);if (mid L) return q_sum(rs[u],rs[v],mid 1,r,L,R);return q_sum(ls[u],ls[v],l,mid,L,R) q_sum(rs[u],rs[v],mid 1,r,L,R);
}
inline LL S(int l,int r){return 1ll * (l r) * (r - l 1) / 2;
}
inline LL q_pre(int u,int v,int L,int R,int k){int ll L,rr R,mid; LL a;while (ll rr){mid ll rr 1;a q_num(u,v,1,N,L,mid);if ((mid - L 1) - a k) rr mid;else ll mid 1;}a q_sum(u,v,1,N,L,ll);return S(L,ll) - a;
}
inline LL q_post(int u,int v,int L,int R,int k){int ll L,rr R,mid,a;while (ll rr){mid ll rr 1 1;a q_num(u,v,1,N,mid,R);if ((R - mid 1) - a k) ll mid;else rr mid - 1;}a q_sum(u,v,1,N,mid,R);return S(ll,R) - a;
}
void work(){int l,r,L,R,a,s; LL ans,b;while (m--){l read(); r read(); L read(); R L r - l; ans 0;if (L 1){a q_num(rt[r],rt[l - 1],1,N,1,L - 1);if (a){s q_sum(rt[r],rt[l - 1],1,N,1,L - 1);b q_pre(rt[r],rt[l - 1],L,R,a);ans b - s;}}a q_num(rt[r],rt[l - 1],1,N,R 1,N);if (a){s q_sum(rt[r],rt[l - 1],1,N,R 1,N);b q_post(rt[r],rt[l - 1],L,R,a);ans s - b;}printf(%lld\n,ans);}
}
int main(){n read(); m read(); N 1000000 n 1; int x;REP(i,n){x read(),modify(rt[i],rt[i - 1],1,N,x);}work();return 0;
}转载于:https://www.cnblogs.com/Mychael/p/9191209.html
