做海报创意网站,珠宝网站设计文案,网站关键词seo优化怎么做,视频链接生成器待我玩会游戏整理下思绪#xff08;分明是想摸鱼 cdq分治是一种用于降维和处理对不同子区间有贡献的离线分治算法 对于常见的操作查询题目而言,时间总是有序的,而cdq分治则是耗费\(O(logq)\)的代价使动态操作化为静态查询问题(the world! 考虑无修改的求逆序对问题 每个元素可…待我玩会游戏整理下思绪分明是想摸鱼 cdq分治是一种用于降维和处理对不同子区间有贡献的离线分治算法 对于常见的操作查询题目而言,时间总是有序的,而cdq分治则是耗费\(O(logq)\)的代价使动态操作化为静态查询问题(the world! 考虑无修改的求逆序对问题 每个元素可定义为\((pos_i,val_i)\),求对每个\((pos_i,val_i)\)有多少个\((pos_j,val_j)\),满足\(pos_jpos_i,val_jval_i\) cdq分治的过程就是令其中一维有序(pos),计算出贡献消除该维度的影响,后面对已遍历的元素只需得知\(val\)的关系即可 因此对于归并过程的merge中假设\([l,mid]\)和\([mid1,r]\)的子区间已经统计完,保证了两个子区间分别有序,那只需再求左子区间对右子区间的贡献即可 比如左子区间中的下标\(p\)和右子区间中的下标\(q\)满足\(val_pval_q\),那么可以得出\(val_{[p...mid]}val_q\),左区间对于右区间中的\(q\)的贡献为\(mid-p1\),统计完后继续维护大区间的有序并pushup即可 而对于有修改(既存在时间变量)的操作,我们需要维护左子区间的修改对右区间查询的影响(因为对于分治,左区间存在是右区间存在的前提),对于查询则需要标记时间的维度\(ansid\) 注意如果\(p\)和\(q\)优先越界的处理上的不同 以及区间查询时一分为二的做法 练手题 Luogu - P3374 题意m次操作单点更新区间查询 我们把原数组的初始值当作插入修改来处理,时间复杂度\(O((mn)log(mn))\) #includebits/stdc.h
#define rep(i,j,k) for(register int ij;ik;i)
#define rrep(i,j,k) for(register int ij;ik;i--)
#define erep(i,u) for(register int ihead[u];~i;inxt[i])
#define print(a) printf(%lld,(ll)(a))
#define printbk(a) printf(%lld ,(ll)(a))
#define println(a) printf(%lld\n,(ll)(a))
using namespace std;
const int MAXN 1.5e611;
typedef long long ll;
const ll MOD 1e97;
const ll INF 1ll60;
unsigned int SEED 19260817;
ll read(){ll x0,f1;register char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}struct QUERY{int pos,val,type;bool operator (const QUERY rhs) const{if(pos!rhs.pos) return posrhs.pos;return typerhs.type;}
}Q[MAXN],tmp[MAXN];
ll ans[MAXN];
void solve(int l,int r){if(lr)return;int midlr1;solve(l,mid);solve(mid1,r);int pl,qmid1,cnt0;ll sum0;while(pmidqr){if(Q[p]Q[q]){if(Q[p].type1) sumQ[p].val;tmp[cnt]Q[p];}else{if(Q[q].type2) ans[Q[q].val]-sum;if(Q[q].type3) ans[Q[q].val]sum;tmp[cnt]Q[q];}}while(pmid) tmp[cnt]Q[p];while(qr){if(Q[q].type2) ans[Q[q].val]-sum;if(Q[q].type3) ans[Q[q].val]sum;tmp[cnt]Q[q];}rep(i,1,cnt) Q[il-1]tmp[i];
}
int main(){int m,n;while(cinnm){int cnt0,ansid0;rep(i,1,n){Q[cnt].posi;Q[cnt].valread();Q[cnt].type1;}rep(i,1,m){int opread();if(op1){Q[cnt].posread();Q[cnt].valread();Q[cnt].type1;}else{int lread();int rread();Q[cnt].posl-1;Q[cnt].valansid;Q[cnt].type2;Q[cnt].posr;Q[cnt].valansid;Q[cnt].type3;}}solve(1,cnt);rep(i,1,ansid) println(ans[i]);}return 0;
} 转载于:https://www.cnblogs.com/caturra/p/9387626.html
