购物网站源码下载,潍坊汇聚网站,旅游网站的功能结构图,建设网站需要展示什么名字ARC077E - guruguru
Solution
考虑每一次改动对于每一个xxx的影响。
设我们要从aaa变到bbb。 当a−x−ba-x-ba−x−b时#xff0c;该次对xxx的贡献为Da,b−Da,x1D_{a,b}-D_{a,x}1Da,b−Da,x1#xff0c;即一个公差为−1-1−1的递减序列#…ARC077E - guruguru
Solution
考虑每一次改动对于每一个xxx的影响。
设我们要从aaa变到bbb。 当a−x−ba-x-ba−x−b时该次对xxx的贡献为Da,b−Da,x1D_{a,b}-D_{a,x}1Da,b−Da,x1即一个公差为−1-1−1的递减序列差分维护ci,dic_i,d_ici,di分别表示当前位置新增的序列个数和这个位置新增序列的aaa的贡献从前往后递推即可。
当a−b−xa-b-xa−b−x时该次对xxx的贡献为Da,bD_{a,b}Da,b即一个定值直接类似前缀和地差分即可。
时间复杂度O(n)O(n)O(n)。
具体实现过程中可以把差分数组扩展两倍然后算iii的贡献和时加上imimim的贡献这样会方便很多。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN300005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
ll s[MAXN],c1[MAXN],d1[MAXN],d2[MAXN],a[MAXN];
signed main()
{int nread(),mread();for (int i1;in;i) a[i]read();for (int i1,l,r,t;in;i){la[i]1,r(a[i]a[i1]?a[i1]m:a[i1])2,tr-l;d1[l]t,c1[l],c1[r]--;l(a[i]a[i1]?a[i]:a[i]m),ra[i1];d2[r1]t-1,d2[l1]-t-1;}ll num0,sum0,ansloo;for (int i1;im*2;i) numc1[i],sumd1[i]-numd2[i],s[i]sum;for (int i1;im;i) upmin(ans,s[i]s[im]);printf(%lld\n,ans);return 0;
}
