猪八戒做网站,南阳网站建站培训,网站建设公司知名企业,江西事件最新消息新闻莫队在知乎回答了一波#xff0c;推荐了一篇博客#xff0c;但原网址挂了。最后凭借搜狗的网页快照#xff0c;我终于一睹这篇博客的真容。 例题 #xff08;2010年国家集训队论文答辩#xff09;小K的袜子 对于询问\([L,R]\)#xff0c;设其中颜色为\(x,y,z...\)的袜子的… 莫队在知乎回答了一波推荐了一篇博客但原网址挂了。最后凭借搜狗的网页快照我终于一睹这篇博客的真容。 例题 2010年国家集训队论文答辩小K的袜子 对于询问\([L,R]\)设其中颜色为\(x,y,z...\)的袜子的个数为\(a,b,c...\) 那么答案即为\(\cfrac{\cfrac{a(a-1)}{2}\cfrac{b(b-1)}{2}\cfrac{c(c-1)}{2}...}{\cfrac{(R-L1)(R-L)}{2}}\) 化简得:\(\cfrac{a^2b^2c^2...x^2-(abcd.....)}{(R-L1)(R-L)}\) 即\(\cfrac{a^2b^2c^2...x^2-(R-L1)}{(R-L1)(R-L)}\) 所以这道题目的关键是求一个区间内每种颜色数目的平方和。 对于一般区间维护类问题一般用线段树但是这题完全不知道线段树怎么做搜索后得知是莫队算法。 莫队算法可以一个可高效解决绝大多数离线无修改区间查询问题的算法。这类问题具体是指如果知道\([L,R]\)的答案时可以在\(O(\mathrm{g}(n))\)的时间下得到\([L,R-1],\)\([L,R1],\)\([L-1,R],\)\([L1,R]\)的答案的话就可以\(O(n\sqrt n · \mathrm{g}(n))\)的时间内求出所有查询。 对于莫队算法我感觉就是暴力。由于预先知道所有的询问因此可以合理的组织计算每个询问的顺序以此来降低复杂度。 假设我们算完\([L,R]\)的答案后现在要算\([L,R]\)的答案。由于可以在\(O(1)\)的时间下得到\([L,R-1],\)\([L,R1],\)\([L-1,R],\)\([L1,R]\)的答案所以计算\([L,R]\)的答案耗时\(|L-L||R-R|\)。如果把询问\([L,R]\)看做平面上的点\(a(L,R)\)询问\([L,R]\)看做点\(b(L,R)\)的话那么时间开销就为两点的曼哈顿距离。 因此如果将每个询问看做平面上的一个点按一定顺序计算每个值那开销就为曼哈顿距离的和。要计算到每个点路径至少会形成一棵树。所以问题就变成了求二维平面的最小曼哈顿距离生成树。 这样只要顺着树边计算一次就OK了可以证明时间复杂度为\(O(n\sqrt{n})\)这个我不会证明但是这种方法的编程复杂度稍微高了一点。 有一个比较优雅的替代品先对序列分块然后对于所有询问按照\(L\)所在块的大小排序如果一样再按照\(R\)排序最后再计算。为什么这样计算就可以降低复杂度呢? 一、\(i\)与\(i1\)在同一块内\(r\)单调递增所以\(r\)是\(O(n)\)的。由于有\(\sqrt{n}\)块,所以这一部分时间复杂度是\(O(n\sqrt{n})\) 二、\(i\)与\(i1\)跨越一块\(r\)最多变化\(n\)由于有\(\sqrt{n}\)块所以这一部分时间复杂度是\(O(n\sqrt{n})\) 三、\(i\)与\(i1\)在同一块内时变化不超过\(\sqrt{n}\)跨越一块也不会超过\(\sqrt{n}\)不妨看作是\(\sqrt{n}\)。由于有n个数所以时间复杂度是\(O(n\sqrt{n})\) 于是就变成了\(O(n\sqrt{n})\)了。 详细过程见代码 #includealgorithm
#includeiostream
#includestring.h
#includestdio.h
#includemath.h
using namespace std;
const int INF0x3f3f3f3f;
const int maxn50010;
typedef long long ll;
ll num[maxn],up[maxn],dw[maxn],ans,aa,bb,cc;
int col[maxn],pos[maxn];
struct qnode
{int l,r,id;
} qu[maxn];
bool cmp(qnode a,qnode b)
{if(pos[a.l]pos[b.l])return a.rb.r;return pos[a.l]pos[b.l];
}
ll gcd(ll x,ll y)
{ll tp;while(tpx%y){xy;ytp;}return y;
}
void update(int x,int d)
{ans-num[col[x]]*num[col[x]];num[col[x]]d;ansnum[col[x]]*num[col[x]];
}
int main()
{int n,m,i,j,bk,pl,pr,id;freopen(in.txt,r,stdin);while(~scanf(%d%d,n,m)){memset(num,0,sizeof num);bkceil(sqrt(1.0*n));for(i1;in;i){scanf(%d,col[i]);pos[i](i-1)/bk;}for(i0;im;i){scanf(%d%d,qu[i].l,qu[i].r);qu[i].idi;}sort(qu,qum,cmp);pl1,pr0;ans0;for(i0;im;i){idqu[i].id;if(qu[i].lqu[i].r){up[id]0,dw[id]1;continue;}if(prqu[i].r){for(jpr1;jqu[i].r;j)update(j,1);}else{for(jpr;jqu[i].r;j--)update(j,-1);}prqu[i].r;if(plqu[i].l){for(jpl;jqu[i].l;j)update(j,-1);}else{for(jpl-1;jqu[i].l;j--)update(j,1);}plqu[i].l;aaans-qu[i].rqu[i].l-1;bb(ll)(qu[i].r-qu[i].l1)*(qu[i].r-qu[i].l);ccgcd(aa,bb);aa/cc,bb/cc;up[id]aa,dw[id]bb;}for(i0;im;i)printf(%I64d/%I64d\n,up[i],dw[i]);}return 0;
} 转载于:https://www.cnblogs.com/P6174/p/7723856.html
