传送门 给你一个序列{ai}\{a_i\}{ai​}，和四个数l1,r1,l2,r2l1,r1,l2,r2l1,r1,l2,r2，求区间[l1,r1]，[l2,r2][l1,r1]，[l2,r2][l1,r1]，[l2,r2]中相同的数有多少对。 当然你不能维护四个指针，考虑容斥原理，我们不妨设f(x,y)f(x,y)f(x,y)为下标为[1,x][1,x][1,x]和下标为[1,y][1,...

传送门 首先，附送本题数据生成器： 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;inline int gen(){ return (rand()<<15)|(rand());}int main(){ srand(time(...

洛谷 LOJ BZOJ 首先，考虑这样一个问题：给你一个序列{ai}\{a_i\}{ai​}，和四个数l1,r1,l2,r2l1,r1,l2,r2l1,r1,l2,r2，求区间[l1,r1]，[l2,r2][l1,r1]，[l2,r2][l1,r1]，[l2,r2]中相同的数有多少对。 这个可以参见我出的一道题：相同颜色对 当然你不能维护四个指针，考虑容斥原理，我们不妨设f(x,y)f(x,...

传送门 小清新莫队题，考虑两个相同的数异或起来会抵消，设sumi=a1⨁a2⨁....⨁aisum_i=a_1⨁a_2⨁....⨁a_isumi​=a1​⨁a2​⨁....⨁ai​我们有ax⨁ax+1⨁....⨁ay=sumy⨁sumx−1a_x ⨁ a_{x+1} ⨁ .... ⨁ a_y=sum_y ⨁ sum_{x-1}ax​⨁ax+1​⨁....⨁ay​=sumy​⨁sumx−1​ ...

传送门 设现在莫队指针l,rl,rl,r维护的区间中不同的数组成的集合为a1,a2,a3...an{a_1,a_2,a_3...a_n}a1​,a2​,a3​...an​ 我们维护这样一个bitset\rm bitsetbitsetsss，对于aia_iai​，s[ai]=1s[a_i]=1s[ai​]=1 Query1 考虑如何实现查询x−y=nx-y=nx−y=n，发现x=y+nx=y...

传送门 首先，假设你会了不带修改的莫队（不会出门右拐百度） 我们来想一想莫队如何支持修改，我们把查询和修改操作离线下来，如图，将查询标为蓝色，将修改标为红色。 假设我们要查询六号查询的答案，考虑哪些修改会影响答案，肯定是在六号之前的修改，且这些修改的下标indindind在六号查询的区间[l,r][l,r][l,r]之内，如图中222，444号修改，要把这些修改全部做完，才能得到正确的结果...