做信息安全的网站,校史网站开发技术,微商怎么做,佛山专业网站设计方案CF848C Goodbye Souvenir
题目描述
Solution
考虑拆贡献#xff0c;把最后一次的下标减去第一次的下标的和拆成每一个点与和它数字相同的上一个点的差的和#xff0c;也就是∑i−pre[i]\sum i-pre[i]∑i−pre[i]。
这样转化之后#xff0c;每一次询问一个区间[l,r][l,r]…CF848C Goodbye Souvenir
题目描述
Solution
考虑拆贡献把最后一次的下标减去第一次的下标的和拆成每一个点与和它数字相同的上一个点的差的和也就是∑i−pre[i]\sum i-pre[i]∑i−pre[i]。
这样转化之后每一次询问一个区间[l,r][l,r][l,r]相当于找到所有满足条件的iii使得l≤i≤rl\leq i \leq rl≤i≤r且pre[i]≥lpre[i]\geq lpre[i]≥l即Ans∑l≤i≤r,l≤pre[i]i−pre[i]Ans\sum_{l\leq i \leq r,l\leq pre[i]}i-pre[i]Ans∑l≤i≤r,l≤pre[i]i−pre[i]这样单个询问就是一个简单的二维数点问题了事实上只需要满足i≤r,l≤pre[i]i \leq r,l\leq pre[i]i≤r,l≤pre[i]即可因为pre[i]pre[i]pre[i]始终小于iii。
再思考如何修改直接CDQCDQCDQ分治即可相当于加上一个时间轴类似一个三维数点。 时间复杂度O(nlg2n)O(nlg^2n)O(nlg2n)。
Code
代码不知道对不对因为luoguluoguluogu交完过了777个点之后UKEUKEUKE了
#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 MAXN600005;
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 Ans[MAXN];
setint S[MAXN];
int pre[MAXN],nxt[MAXN],whp[MAXN],whn[MAXN],a[MAXN],n,m,num0,Num0;
struct Qnode{ int id,opt,x,y,c; } Q[MAXN];
int compare(Qnode x,Qnode y)
{if (x.opt!y.opt) return x.opty.opt;return x.opt?(x.yy.y):(x.xy.x);
}
int compareid(Qnode x,Qnode y) { return x.idy.id; }
void Init()
{nread(),mread();for (int i1;in;i) a[i]read();for (int i1;in;i) whp[i]0,whn[i]n1;for (int i1;in;i) pre[i]whp[a[i]],whp[a[i]]i;for (int in;i1;i--) nxt[i]whn[a[i]],whn[a[i]]i;for (int i1;in;i) Q[num](Qnode){num,0,i,pre[i],i-pre[i]},S[a[i]].insert(i);while (m--){int optread(),yread(),zread();if (opt1) {if (pre[y]!0) nxt[pre[y]]nxt[y],Q[num](Qnode){num,0,y,pre[y],pre[y]-y};if (nxt[y]!n1) pre[nxt[y]]pre[y],Q[num](Qnode){num,0,nxt[y],y,y-nxt[y]};if (pre[y]!0nxt[y]!n1) Q[num](Qnode){num,0,nxt[y],pre[y],nxt[y]-pre[y]};S[a[y]].erase(y),a[y]z;setint::iterator itS[z].lower_bound(y);nxt[y](it!S[z].end())?(*it):n1;pre[y](it!S[z].begin())?(*(--it)):0;if (pre[y]!0) nxt[pre[y]]y,Q[num](Qnode){num,0,y,pre[y],y-pre[y]};if (nxt[y]!n1) pre[nxt[y]]y,Q[num](Qnode){num,0,nxt[y],y,nxt[y]-y};if (pre[y]!0nxt[y]!n1) Q[num](Qnode){num,0,nxt[y],pre[y],pre[y]-nxt[y]}; S[z].insert(y);}else Q[num](Qnode){num,1,y,z,Num};}
// for (int i1;inum;i) coutQ[i].id Q[i].opt Q[i].x Q[i].y Q[i].cendl;
}
struct Binary_Index_Tree
{ll s[MAXN1];int lowbit(int x) { return x(-x); }void change(int x,int y){ if (!x) return; for (;xn;xlowbit(x)) s[x]y; }ll query(int x) { ll ans0; for (;x;x-lowbit(x)) anss[x]; return ans; }
} bit;
void Solve(int l,int r)
{if (lr) return;int mid(lr)1;Solve(l,mid),Solve(mid1,r);sort(Ql,Qmid1,compare);sort(Qmid1,Qr1,compare);int Ll;for (int imid1;ir;i)if (Q[i].opt){while (Lmid(Q[L].opt||Q[L].xQ[i].y)) { if (!Q[L].opt) bit.change(Q[L].y,Q[L].c); L; }Ans[Q[i].c]bit.query(n)-bit.query(Q[i].x-1);}for (int il;iL;i) if (!Q[i].opt) bit.change(Q[i].y,-Q[i].c);
}
int main()
{Init();Solve(1,num);for (int i1;iNum;i) printf(%lld\n,Ans[i]);return 0;
}
