empty
分类 笔记 下的文章
Ds100p -「数据结构百题」61~70
61.P5355 [Ynoi2017]由乃的玉米田
由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。
这排玉米一共有 $N$ 株，它们的高度参差不齐。
由乃认为玉米田不美，所以她决定出个数据结构题
这个题是这样的：
给你一个序列 $a$，长度为 $n$，有 $m$ 次操作，每次询问一个区间是否可以选出两个数它们的差为 $x$，或者询问一个区间是否可以选出两个数它们的和为 $x$，或者询问一个区间是否可以选出两个数它们的乘积为 $x$ ，或者询问一个区间是否可以选出两个数它们的商为 $x$（没有余数） ，这四个操作分别为操作 $1,2,3,4$。
选出的这两个数可以是同一个位置的数。
题意简述
见题面
题解
前三个操作就是小清新人渣的本愿。
这里简单讲解一下。
记录两个 bitset cla 和 inv。
我们考虑莫队。
cla[x]==1 表示 $x$ 这个数出现过。
inv[x]==1 表示 $100000-x$ 这个数出现过。
这两个 bitset 的维护很简单，就是在莫队的加减贡献操作里改就行了。
对于第一个减法的判断，我们的答案就是 ((cla<<x)&cla) 是否为 0。
如果为 0 的话表示应该输出有解。
正确性很好得到。
比如我们的询问是是否存在 $a,b$ 使得 $a-b=x$。
那么我们只需要存在 $a$ 以及 $a-x$ 即可。
第二个加法的判断也差不多，看作是加一个负数即可，判断是 ((cla<<(100000-x)&inv))。
第三个乘法的判断直接暴力枚举因子 $i$，判断 $i,\frac{x}{i}$ 是否同时存在即可。($i\mid x$)。
由于值域和 $n,m$ 同阶，所以我们的复杂度是对的。
对于第四个操作我们直接从乘法贺过来。
枚举一个 $i$，从 1 开始，终止条件为 $i\times x\le100000$。
其中 $x$ 为当前询问给出的商。
然后直接判断是否同时存在 $i$ 和 $i\times x$ 即可。
在 $x\ge\sqrt{n}$ 的时候我们的复杂度是对的。
那么 $x<\sqrt{n}$ 的时候我们就换一种方法吧。
我们枚举一个 $x\in[1,\sqrt{100000}]$。
然后维护两个数组 pre 和 mxp。
在 $x$ 的枚举里面我们再枚举一个 $i\in[1,n]$。
然后 pre[i] 表示 $a_{i}$ 的上一次出现位置。
mxp[i] 扫描到 $i$ 的时候出现了满足 $a\div b=x$ 的最右位置。
维护的具体方法看注释吧。
这道题就完了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
const int Maxn = 1e5 + 5, Maxs = 400 + 5, Maxv = 310;
int n, m, each, cube, isa[Maxn], cnt[Maxn], ans[Maxn], pre[Maxn], mxp[Maxn], bel[Maxn], lps[Maxs], rps[Maxs];
struct Query
{
int t, l, r, x, id;
Query() {}
Query(int t1, int t2, int t3, int t4, int t5)
{
t = t1;
l = t2;
r = t3;
x = t4;
id = t5;
}
};
struct Special
{
int l, r, id;
Special() {}
Special(int t1, int t2, int t3)
{
l = t1;
r = t2;
id = t3;
}
};
vector < Query > Mq; // Mo's Algorithm | Query
vector < Special > Vq[Maxn]; // Violence | Query
bitset < Maxn > cla, inv; // classic | inverse
bool cmp(const Query &one, const Query &ano)
{
if (bel[one.l] != bel[ano.l]) return one.l < ano.l;
else if (bel[one.l] & 1) return one.r < ano.r;
else return one.r > ano.r;
}
void Plus_Cont(int x)
{
x = isa[x];
if (cnt[x] == 0)
{
cla[x] = 1;
inv[100000 - x] = 1;
}
++cnt[x];
}
void Mins_Cont(int x)
{
x = isa[x];
--cnt[x];
if (cnt[x] == 0)
{
cla[x] = 0;
inv[100000 - x] = 0;
}
}
void Pare_v1()
{
int l = 1, r = 0;
for (auto it : Mq)
{
while (l > it.l) Plus_Cont(--l);
while (l < it.l) Mins_Cont(l++);
while (r > it.r) Mins_Cont(r--);
while (r < it.r) Plus_Cont(++r);
if (it.t == 1) ans[it.id] = ((cla << it.x) & cla).any();
else if (it.t == 2) ans[it.id] = ((cla << (100000 - it.x)) & inv).any();
else if (it.t == 3)
{
bool flag = 0;
for (int i = 1; i * i <= it.x; ++i)
{
if (it.x % i == 0 && cla.test(i) && cla.test(it.x / i))
{
ans[it.id] = 1;
flag = 1;
break;
}
}
if (flag == 0) ans[it.id] = 0;
}
else
{
bool flag = 0;
for (int i = 1; i * it.x <= 100000; ++i)
{
if (cla.test(i) && cla.test(i * it.x))
{
ans[it.id] = 1;
flag = 1;
break;
}
}
if (flag == 0) ans[it.id] = 0;
}
}
}
void Pare_v2()
{
for (int x = 1; x <= Maxv; ++x)
{
if (Vq[x].empty()) continue;
int now = 0;
for (int i = 1; i <= n; ++i)
{
int y = isa[i];
pre[y] = i;
if (x * y <= 100000) now = max(now, pre[x * y]);
if (y % x == 0) now = max(now, pre[y / x]);
mxp[i] = now;
}
for (auto it : Vq[x])
{
if (it.l <= mxp[it.r]) ans[it.id] = 1;
else ans[it.id] = 0;
}
memset(pre, 0, sizeof pre);
memset(mxp, 0, sizeof mxp);
}
}
char ANS[2][10] = { "yumi", "yuno" };
signed main()
{
scanf("%d %d", &n, &m);
each = 320;
cube = (n - 1) / each + 1;
for (int i = 1; i <= n; ++i) scanf("%d", &isa[i]);
for (int i = 1; i <= cube; ++i)
{
lps[i] = rps[i - 1] + 1;
rps[i] = rps[i - 1] + each;
if (i == cube) rps[i] = n;
for (int j = lps[i]; j <= rps[i]; ++j) bel[j] = i;
}
for (int i = 1, t, l, r, x; i <= m; ++i)
{
scanf("%d %d %d %d", &t, &l, &r, &x);
if (t == 4 && x <= Maxv) Vq[x].emplace_back(Special(l, r, i));
else Mq.emplace_back(Query(t, l, r, x, i));
}
sort(Mq.begin(), Mq.end(), cmp);
Pare_v1(), Pare_v2();
for (int i = 1; i <= m; ++i) puts(ANS[ans[i]]);
return 0;
}62.P5354 [Ynoi2017]由乃的OJ
第一行两个整数 $n,m$。
第二行 $n$ 个整数表示序列 $a$。
接下来 $m$ 行，每行四个整数：
1 l r x：把区间 $[l,r]$ 所有大于 $x$ 的数减去 $x$。2 l r x：查询区间 $[l,r]$ 内的 $x$ 的出现次数。
题目里讲得非常清楚，就是把 睡觉困难综合征 搬到树上了。
那我们先回想一下 睡觉困难综合征 是怎么做的：
首先我们设了两个值，一个在二进制下全是 $1$ （下文中为 $mx$ ），一个全是 $0$ （下文中为 $mn$ ）。
然后我们直接对序列中每一个操作用这两个值进行模拟。
因为二进制运算每个位独立，所以我们可以得到一开始的时候每个位选 $0$ 或 $1$ 时最后能够得到 $0$ 还是 $1$ 。
然后我们就贪心进行选取 $0/1$ 就好了。
先考虑一个序列如何动态维护这个问题。
我们可以开一棵线段树，维护区间内一开始是 $mx$ 和 $mn$ ，一直把这个区间模拟完之后的结果。
那么问题来了，如何合并两个区间的答案呢？
我们先按位分析：现在知道这位选 $1$ 和 $0$ 分别在两边会得到什么结果，那我们先模拟这位选什么，用在左边的结果再拿到右边去看放进去会得到什么结果。这样就可以得到整个区间这位选 $1$ 或 $0$ 的结果了。
那么我们一共枚举最多 $64$ 位， $64$ 的常数瞬间爆炸，所以肯定不能按位枚举。
想一想如果优化这个过程。
我们可以先得到左边全选 $1$ 或 $0$ 时会得到的结果上哪些位是 $1$ ，哪些位是 $0$ 。然后去右边区间看下这些是 $1$ 的位上哪些又会变成 $0$ 或 $1$ ，是 $0$ 的位上哪些又是 $1$ 或 $0$ 。
首先设 $tmp1$ 表示经过左边之后是 $1$ 的位置， $tmp0$ 表示经过左边之后是 $0$ 的位置。
那么 tmp1=now,tmp0=now;（ $now$ 表示当前左边全选 $0$ 或 $1$ 的结果）
然后得到答案 ans=(tmp1&right1)|(tmp0&right0)。（ $right0/1$ 表示右边全选 $0/1$ 的结果）
就相当于把左边结果的 $0$ 和 $1$ 分别处理，把是$0$或$1$的位上的右边的结果直接搬过来。
因为这一位经过左边后变成了 $0/1$，所以这一位经过右边之后就应该是右边一开始这位选 $0/1$ 的结果。
这样我们就做到了 $\operatorname{O}(1)$ 合并两个区间的结果。
最后再用树链剖分把这个过程搬到树上就好了。
这道题的两个端点的顺序是有影响的。所以要在树剖里分类讨论，还要维护区间倒着来的结果。
细节很多WA了很久，不愧是Ynoi
代码：
#include<cstdio>
#include<vector>
using namespace std;
vector<unsigned long long> e[100010];
struct node
{
unsigned long long one,zero;
}nodes[400010],exnodes[400010],emp,ret,exret;//nodes是正着来，exnodes是反着来
const unsigned long long cone=1;//1常量，免得1<<i爆掉
unsigned long long mx,mn;//全为1和全为0的量
unsigned long long n,m,k,opx[100010],op[100010],u,v,opt,opa,opb,opc;
unsigned long long siz[100010],son[100010],dep[100010],fa[100010],hb[100010],dfn[100010],ton[100010],cnt;
bool flag,exflag;
void dfs1(unsigned long long x,unsigned long long las)
{
fa[x]=las;
dep[x]=dep[las]+cone;
siz[x]=cone;
for(unsigned long long i=0;i<e[x].size();++i)
{
unsigned long long y=e[x][i];
if(y^las)
{
dfs1(y,x);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y]) son[x]=y;
}
}
}
void dfs2(unsigned long long x,unsigned long long las,bool heavy)
{
dfn[x]=++cnt;
ton[cnt]=x;
if(heavy) hb[x]=hb[las];
else hb[x]=x;
if(son[x]) dfs2(son[x],x,1);
for(unsigned long long i=0;i<e[x].size();++i)
{
unsigned long long y=e[x][i];
if((y^las)&&(y^son[x])) dfs2(y,x,0);
}
}
node merge(node one,node ano)
{
node res=emp;
unsigned long long tmp1=one.one;
unsigned long long tmp0=~tmp1;
res.one=(tmp1&ano.one)|(tmp0&ano.zero);
tmp1=one.zero;
tmp0=~tmp1;
res.zero=(tmp1&ano.one)|(tmp0&ano.zero);//全选0/1分别维护
return res;
}
void build(unsigned long long l,unsigned long long r,unsigned long long x)
{
if(l^r)
{
unsigned long long mid=(l+r)>>cone;
build(l,mid,x<<cone);
build(mid+cone,r,x<<cone|cone);
nodes[x]=merge(nodes[x<<cone],nodes[x<<cone|cone]);
exnodes[x]=merge(exnodes[x<<cone|cone],exnodes[x<<cone]);//反着来的肯定也要反着合并
}
else
{
nodes[x]=exnodes[x]=emp;
if(op[ton[l]]==cone)//初值直接模拟就好
{
nodes[x].one&=opx[ton[l]];
exnodes[x].one&=opx[ton[l]];
nodes[x].zero&=opx[ton[l]];
exnodes[x].zero&=opx[ton[l]];
}
else if(op[ton[l]]==2)
{
nodes[x].one|=opx[ton[l]];
exnodes[x].one|=opx[ton[l]];
nodes[x].zero|=opx[ton[l]];
exnodes[x].zero|=opx[ton[l]];
}
else
{
nodes[x].one^=opx[ton[l]];
exnodes[x].one^=opx[ton[l]];
nodes[x].zero^=opx[ton[l]];
exnodes[x].zero^=opx[ton[l]];
}
}
}
void update(unsigned long long l,unsigned long long r,unsigned long long x,unsigned long long pos,unsigned long long oper,unsigned long long val)
{
if(l^r)
{
unsigned long long mid=(l+r)>>cone;
if(pos<=mid) update(l,mid,x<<cone,pos,oper,val);
else update(mid+cone,r,x<<cone|cone,pos,oper,val);
nodes[x]=merge(nodes[x<<cone],nodes[x<<cone|cone]);
exnodes[x]=merge(exnodes[x<<cone|cone],exnodes[x<<cone]);
}
else
{
op[ton[l]]=oper;
opx[ton[l]]=val;
nodes[x]=exnodes[x]=emp;
if(op[ton[l]]==cone)
{
nodes[x].one&=opx[ton[l]];
exnodes[x].one&=opx[ton[l]];
nodes[x].zero&=opx[ton[l]];
exnodes[x].zero&=opx[ton[l]];
}
else if(op[ton[l]]==2)
{
nodes[x].one|=opx[ton[l]];
exnodes[x].one|=opx[ton[l]];
nodes[x].zero|=opx[ton[l]];
exnodes[x].zero|=opx[ton[l]];
}
else
{
nodes[x].one^=opx[ton[l]];
exnodes[x].one^=opx[ton[l]];
nodes[x].zero^=opx[ton[l]];
exnodes[x].zero^=opx[ton[l]];
}
}
}
void find(unsigned long long l,unsigned long long r,unsigned long long x,unsigned long long fr,unsigned long long ba)//y用的find
{
if(l>ba||r<fr) return;
if(l>=fr&&r<=ba)
{
if(!flag)
{
ret=nodes[x];
flag=cone;
}
else ret=merge(nodes[x],ret);//LCA到y中是dfs序从小到大，y的dfs序大，所以要放到后面，并和正序的结果合并
}
else
{
unsigned long long mid=(l+r)>>cone;
find(mid+cone,r,x<<cone|cone,fr,ba);//y放到后面
find(l,mid,x<<cone,fr,ba);
}
}
void exfind(unsigned long long l,unsigned long long r,unsigned long long x,unsigned long long fr,unsigned long long ba)//x用的exfind
{
if(l>ba||r<fr) return;
if(l>=fr&&r<=ba)
{
if(!exflag)
{
exret=exnodes[x];
exflag=cone;
}
else exret=merge(exret,exnodes[x]);//x到LCA中是dfs序从大到小，x的dfs序大，所以要放到后面，并和倒序的结果合并
}
else
{
unsigned long long mid=(l+r)>>cone;
exfind(mid+cone,r,x<<cone|cone,fr,ba);//x放到后面
exfind(l,mid,x<<cone,fr,ba);
}
}
node LCA(unsigned long long x,unsigned long long y)
{
unsigned long long fx=hb[x],fy=hb[y];
flag=exflag=0;//如果之前没有值，就直接把值赋给ret/exret
ret=exret=emp;
while(fx^fy)
{
if(dep[fx]>dep[fy])//分类讨论
{
exfind(cone,n,cone,dfn[fx],dfn[x]);//x这边是从x到LCA往上，但x的dfs序更大
x=fa[fx];
fx=hb[x];
}
else
{
find(cone,n,cone,dfn[fy],dfn[y]);//y这边是从LCA到y往下，但y的dfs序更大
y=fa[fy];
fy=hb[y];
}
}
if(dep[x]<dep[y]) find(cone,n,cone,dfn[x],dfn[y]);
else exfind(cone,n,cone,dfn[y],dfn[x]);
return merge(exret,ret);//x这边在前面
}
unsigned long long solve(node how,unsigned long long lim)//贪心选取
{
unsigned long long res=0,used=0;
for(unsigned long long i=k-1;i>=0;--i)
{
if(how.zero&(cone<<i)) res+=(cone<<i);
else if((how.one&(cone<<i))&&used+(cone<<i)<=lim)
{
res+=(cone<<i);
used+=(cone<<i);
}
if(i==0) break;
}
return res;
}
int main()
{
scanf("%llu %llu %llu",&n,&m,&k);
mx=-cone;
mn=0;
emp.one=mx;
emp.zero=mn;
for(unsigned long long i=cone;i<=n;++i) scanf("%llu %llu",&op[i],&opx[i]);
for(unsigned long long i=cone;i<n;++i)
{
scanf("%llu %llu",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(cone,cone);
dfs2(cone,cone,0);
build(cone,n,cone);
for(unsigned long long i=cone;i<=m;++i)
{
scanf("%llu %llu %llu %llu",&opt,&opa,&opb,&opc);
if(opt==2) update(cone,n,cone,dfn[opa],opb,opc);
else printf("%llu\n",k?solve(LCA(opa,opb),opc):0);
}
return 0;
}63.P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III
给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的众数的出现次数，强制在线。
题意简述
区间众数出现次数强制在线。
题解
三个 YLST 中比较清新的一个分块。
比较重点的地方在于询问散块的处理。
先离散化一下序列。
我们首先预处理出来一个 vector 数组 fur[i]，fur[i] 里面依次存的是所有 isa[i]（即这个序列，详见代码）的出现位置，再预处理一个 pos[i] 表示在当前第 $i$ 位时 fur[i] 的大小也就是一共出现了多少个 isa[i]。由于 vector 的下标是从 $0$ 开始的，所以所有的 pos[i] 都需要减个一。
然后询问处理整块的时候，我们先假设当前询问的区间是 [opl,opr]，然后把当前询问的答案 res 先置为 App[bel[opl] + 1][bel[opr] - 1]。
然后来考虑散块，在处理出的 vector 数组中判断即可。
设散块处理到数 isa[i]，那么如果存在 pos[i] + res <= fur[isa[i]].size() - 1 且 fur[isa[i]][pos[i] + res] <= opr，那么则说明这个数出现了至少 res + 1 次，将 res 加一即可。
由于 res 最多加不超过 $\Theta(2\sqrt{n})$ 次，所以复杂度是对的。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 5e5 + 5, MAXM = 720 + 5;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1 ++ )
template<typename _T>
void read( _T &x ){
x = 0; char c = getchar( ); _T f = 1;
while( c < '0' || c > '9' ){ if( c == '-' ) f = -1; c = getchar( ); }
while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
x *= f;
}
template<typename _T>
void write( _T x ){
if( x < 0 ){ putchar( '-' ); x = -x; }
if( x > 9 ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &one, _T &another ){ int temp = one; one = another; another = temp; }
template<typename _T>
_T MIN( _T one, _T another ){ return one > another ? another : one; }
template<typename _T>
_T MAX( _T one, _T another ){ return one > another ? one : another; }
int N, M;
int cube, each, kase, isa[MAXN], cnt[MAXN], pos[MAXN], vis[MAXN], bel[MAXN];
int lps[MAXM], rps[MAXM], app[MAXM], App[MAXM][MAXM];
vector<int> disc, fur[MAXN];
int getID( int x ){ return lower_bound( disc.begin( ), disc.end( ), x ) - disc.begin( ) + 1; }
void build( ){
for( int i = 1; i <= cube; ++ i ){
kase ++;
for( int j = lps[i]; j <= rps[i]; ++ j ){
if( vis[isa[j]] != kase ) cnt[isa[j]] = 0;
cnt[isa[j]] ++; app[i] = MAX( app[i], cnt[isa[j]] );
vis[isa[j]] = kase;
}
}
memset( cnt, 0, sizeof( cnt ) );
for( int i = 1; i <= cube; ++ i ){
kase ++;
for( int j = i; j <= cube; ++ j ){
App[i][j] = App[i][j - 1];
for( int k = lps[j]; k <= rps[j]; ++ k ){
if( vis[isa[k]] != kase ) cnt[isa[k]] = 0;
cnt[isa[k]] ++; App[i][j] = MAX( App[i][j], cnt[isa[k]] );
vis[isa[k]] = kase;
}
}
}
memset( cnt, 0, sizeof( cnt ) );
}
int query( int opl, int opr ){
if( bel[opl] == bel[opr] ){
int res = 0; kase ++;
for( int i = opl; i <= opr; ++ i ){
if( vis[isa[i]] != kase ) cnt[isa[i]] = 0;
cnt[isa[i]] ++; res = MAX( res, cnt[isa[i]] );
vis[isa[i]] = kase;
}
return res;
}
int res = 0;
// res = App[bel[opl] + 1][bel[opr] - 1];
for( int i = bel[opl] + 1; i < bel[opr]; ++ i ) res += app[i];
// for( int i = bel[opl] + 1; i < bel[opr]; ++ i ) res += App[i][i];
for( int i = opl; i <= rps[bel[opl]]; ++ i ){
int lim = fur[isa[i]].size( ) - 1;
while( pos[i] + res <= lim && fur[isa[i]][pos[i] + res] <= opr ) res ++;
}
for( int i = lps[bel[opr]]; i <= opr; ++ i ){
while( pos[i] - res >= 0 && fur[isa[i]][pos[i] - res] >= opl ) res ++;
}
return res;
}
signed main( ){
read( N ); read( M ); each = 720; cube = ( N - 1 ) / each + 1;
for( int i = 1; i <= N; ++ i ){ read( isa[i] ); disc.push_back( isa[i] ); }
sort( disc.begin( ), disc.end( ) );
disc.erase( unique( disc.begin( ), disc.end( ) ), disc.end( ) );
for( int i = 1; i <= N; ++ i ){
isa[i] = getID( isa[i] );
fur[isa[i]].push_back( i );
pos[i] = fur[isa[i]].size( ) - 1;
}
for( int i = 1; i <= cube; ++ i ){
lps[i] = rps[i - 1] + 1; rps[i] = rps[i - 1] + each;
if( i == cube ) rps[i] = N;
for( int j = lps[i]; j <= rps[i]; ++ j ) bel[j] = i;
}
build( );
int Ans = 0, opl, opr;
while( M -- > 0 ){
read( opl ); read( opr ); opl ^= Ans; opr ^= Ans;
Ans = 0; if( opl > opr ) swapp( opl, opr );
write( Ans = query( opl, opr ) ); putchar( '\n' );
}
return 0;
}64.「LibreOJ β Round #4」框架
没想到吧，我他娘的更新了
看到这道题
WGY说：bitset优化轻松过掉
LJS说：bitset优化裸题
ljs说：暴力打表能过！
那么这里是数据结构一百题，怎么能用这些方法呢？
所以我们来看看这道题吧：
有一个 $n\times m$的矩形框架，但其中有些边被删除了。$\operatorname{qmqmqm}$ 想知道剩余部分中还有多少完整的正方形。
$2\leq n,m\leq 10^3$
先不看数据范围
考虑最朴素的暴力
三重循环分别枚举：左上角横坐标，左上角纵坐标，正方形边长
时间复杂度$n^3$
妥妥超时
那我们怎么优化呢
开一个数组记录一个点往左和往上最多能往上走几条边，由于是正方形，取这两个值中较小的一个就行了。
那么我们可以知道以每个点为右下角时正方形的边长最大值。
只需要再判断左上角是否能够走那么长了。
我们发现，以一个点为正方形的右下角时，可能的左上角位置在一条直线上，那么我们可以直接处理这一条直线。
每个点有往左上可以走到的最大距离，我们可以求出每个点往右下走的最大距离。如果两个点可以互相到达，那么它们就可以作为一个正方形的两个顶点。
我们可以用主席树解决上面的问题：版本 $i$ 记录第 $1$ 到 $i$ 的点往前最多可以到达哪个点。
我们只在最远点上加个 $1$。因为之后查询会考虑到的。
再枚举每个点，查询从它后面到它往后最多能跳到的点中有多少点能够跳到它。
也就是这个区间的点中有多少个点能跳到的最远点小于等于它。
为什么有小于？因为如果能跳到更前面，那肯定能跳到这里。这就是之前只在最远点上加 $1$ 的原因。（其实区间加单点查也是可以的）
对于前面记录最多能跳到哪里的数组，我们用二分来获取它。
总时间复杂度：
二分：$n^2logn$（每个点一次二分）
主席树:$n^2logn$（主席树对每个点操作一次）
总：$n^2logn$（因为二分和主席树是两个分开的部分）
跑不过 $bitset$ 嘤嘤嘤...
代码：（注意细节）
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,lsum[1010][1010],hsum[1010][1010],dp[1010][1010],root[1010],ans,tot;
struct node
{
int l,r,num;
}nodes[100010];
int search(int l,int r,int x,int y)
{
while(l+1<r)
{
int mid=(l+r)>>1;
if(lsum[x][y]-lsum[x-mid][y]==mid&&hsum[x][y]-hsum[x][y-mid]==mid) l=mid;
else r=mid;
}
return l;
}
int exsearch(int l,int r,int x,int y)
{
while(l+1<r)
{
int mid=(l+r)>>1;
if(lsum[x+mid][y]-lsum[x][y]==mid&&hsum[x][y+mid]-hsum[x][y]==mid) l=mid;
else r=mid;
}
return l;
}
void ins(int l,int r,int pre,int &now,int pos)
{
now=++tot;
nodes[now]=nodes[pre];
++nodes[now].num;
if(l^r)
{
int mid=(l+r)>>1;
if(pos<=mid) ins(l,mid,nodes[pre].l,nodes[now].l,pos);
else ins(mid+1,r,nodes[pre].r,nodes[now].r,pos);
}
}
int find(int l,int r,int v1,int v2,int fr,int ba)
{
if(l>ba||r<fr) return 0;
if(l>=fr&&r<=ba) return nodes[v2].num-nodes[v1].num;
int mid=(l+r)>>1;
return find(l,mid,nodes[v1].l,nodes[v2].l,fr,ba)+find(mid+1,r,nodes[v1].r,nodes[v2].r,fr,ba);
}
void solve(int x,int y)
{
tot=0;
int siz=min(n-x,m-y)+1;
for(int i=x,j=y,k=1;i<=n&&j<=m;++i,++j,++k) ins(1,siz,root[k-1],root[k],k-dp[i][j]);
for(int i=x,j=y,k=1;i<=n&&j<=m;++i,++j,++k) ans+=find(1,siz,root[k],root[k+exsearch(0,min(n-i,m-j)+1,i,j)],1,k);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=2;j<=m;++j)
{
scanf("%d",&hsum[i][j]);
hsum[i][j]+=hsum[i][j-1];
}
}
for(int i=2;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&lsum[i][j]);
lsum[i][j]+=lsum[i-1][j];
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
dp[i][j]=search(0,min(i,j),i,j);
}
}
for(int i=1;i<=m;++i) solve(1,i);
for(int i=2;i<=n;++i) solve(i,1);
printf("%d",ans);
return 0;
}65. P4689 [Ynoi2016]这是我自己的发明
我首先认为这是 SNOI2017 一个简单的询问 搬到树上。
我们传统地把此题分为两个 $\texttt{pass}$，一个询问，一个修改。
- $\texttt{pass 1}$：询问
我直接按 一个简单的询问 的方法讲。其实是把以前的题解 copy 过来了。
由于是出现次数，满足区间加减性，所以我们可以这样表达 $\mathrm{get}(l,r,x)$（省略 $x$）:
$$ \mathrm{get}(l,r)=\mathrm{get}(1,r)-\mathrm{get}(1,l-1) $$
那么我们代进原式，化一波式子（$\mathrm{get}(p)=\mathrm{get}(1,p,x)$）：
$$ \sum_{i=1}^{\infty}\mathrm{get}(l_{1},r_{1},x)\times\mathrm{get}(l_{2},r_{2},x) $$
$$ \sum_{i=1}^{\infty}(\mathrm{get}(1,r_{1})-\mathrm{get}(1,l_{1}-1))\times(\mathrm{get}(1,r_{2})-\mathrm{get}(1,l_{2}-1)) $$
$$ \sum_{i=1}^{\infty}\mathrm{get}(r_{1})\times\mathrm{get}(r_{2})-\mathrm{get}(r_{1})\times\mathrm{get}(l_{2}-1)-\mathrm{get}(l_{1}-1)\times\mathrm{get}(r_{2})+\mathrm{get}(l_{1}-1))\times\mathrm{get}(l_{2}-1) $$
$$ \mathrm{let}\ F(x,y)=\sum_{d}\mathrm{get}(1,l,d)\times\mathrm{get}(1,r,d) $$
则答案为:
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
考虑怎么更新，比如从 $l$ 更新到 $l+1$，则：
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l+1)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r)+\mathrm{cont}(a_{l}) $$
其中 $\mathrm{cont}(a_{l})$ 表示 $a_{l}$ 的出现次数。
则我们就知道怎么更新了，由于我们维护和的是前缀信息，所以姿势和普通莫队有点不一样。
维护两个数组 cntl[x] 和 cntr[y] 表示答案式子
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
子树的话直接 DFS 序拍到序列上。
- $\texttt{pass 2}$：修改
现在我们面临着查询操作我们是用莫队整的，但这个修改貌似不单纯。其实也是从树剖模板缝合过来的。
分类讨论，设我们当前要换的根为 $rt$，现在来处理询问，设查询的节点为 $u$，$\text{LCA}(u,v)$ 为节点 $u$ 和节点 $v$ 的最近公共祖先。
- 如果 $rt=u$，则我们直接对整棵树进行查询。
- 如果 $\text{LCA}(u,rt)\neq u$，此时修改不影响查询。
- 如果 $\text{LCA}(u,rt)=u$，此时 $rt$ 在 $u$ 的子树里，那么需要查询的地方就很明确了，后面的步骤显然。
于是我们不需要实际的去处理这个修改，然后就可以直接莫队了。
（整体感觉是个 原题+假上树+树剖模板 的缝合题）
/* Clearink */
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5e5 + 5, MAXM = 1e6 + 5;
int rint () {
int x = 0, f = 1; char c = getchar ();
for ( ; c < '0' || c > '9'; c = getchar () ) f = c == '-' ? -1 : f;
for ( ; c >= '0' && c <= '9'; c = getchar () ) x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
return x * f;
}
template<class _T>
void wint ( _T x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( x > 9 ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
template<class _T> void swapp ( _T& x, _T& y ) { _T w = x; x = y; y = w; }
struct GraphSet {
int to, nx;
GraphSet () : to ( 0 ), nx ( 0 ) {}
GraphSet ( const int a, const int b ) : to ( a ), nx ( b ) {}
} asg[MAXN * 2];
struct Quest {
int l, r, ID, x;
Quest () : l ( 0 ), r ( 0 ), ID ( 0 ), x ( 0 ) {}
Quest ( const int a, const int b, const int c, const int d ) : l ( a ), r ( b ), ID ( c ), x ( d ) {}
} asq[MAXM * 8], itls[MAXN];
LL cur = 0, ans[MAXM], buc1[MAXN], buc2[MAXN];
int rt, pos[MAXN], blo = 320, col[MAXN], freq;
int n, m, bgn[MAXN], cnt, sjc, segl[MAXN], segr[MAXN], kfa[MAXN][21], a[MAXN], dept[MAXN], pri[MAXN], len;
void addE ( const int u, const int v ) { asg[++ cnt] = GraphSet ( v, bgn[u] ), bgn[u] = cnt; }
bool existcmp ( const Quest& one, const Quest& ano ) { return pos[one.l] == pos[ano.l] ? one.r < ano.r : one.l < ano.l; }
void dfs ( const int u, const int lst ) {
kfa[u][0] = lst, dept[u] = dept[lst] + 1;
segl[u] = ++ sjc, col[sjc] = a[u];
for ( int i = 1; i <= 20; ++ i ) kfa[u][i] = kfa[kfa[u][i - 1]][i - 1];
for ( int i = bgn[u]; i; i = asg[i].nx ) {
int v = asg[i].to;
if ( v == lst ) continue;
dfs ( v, u );
}
segr[u] = sjc;
}
int calcKAC ( int u, int k ) {
for ( int i = 20; ~ i; -- i ) {
if ( k >= ( 1 << i ) ) k -= ( 1 << i ), u = kfa[u][i];
}
return u;
}
int calcLCA ( int u, int v ) {
if ( dept[u] < dept[v] ) swapp ( u, v );
for ( int i = 20; ~ i; -- i ) {
if ( dept[kfa[u][i]] >= dept[v] ) u = kfa[u][i];
}
if ( u == v ) return u;
for ( int i = 20; ~ i; -- i ) {
if ( kfa[u][i] != kfa[v][i] ) u = kfa[u][i], v = kfa[v][i];
}
return kfa[u][0];
}
void initial () {
for ( int i = 1; i <= n; ++ i ) pos[i] = ( i - 1 ) / blo + 1;
sort ( pri + 1, pri + 1 + n );
len = unique ( pri + 1, pri + 1 + n ) - pri - 1;
for ( int i = 1; i <= n; ++ i ) a[i] = lower_bound ( pri + 1, pri + 1 + len, a[i] ) - pri;
dfs ( 1, 0 );
}
void splitASdrug ( const int u, int& ils ) {
if ( u == rt ) itls[++ ils] = Quest ( 1, n, 0, 0 );
else {
int lca = calcLCA ( u, rt );
if ( lca != u ) itls[++ ils] = Quest ( segl[u], segr[u], 0, 0 );
else {
int ar = calcKAC ( rt, dept[rt] - dept[u] - 1 );
if ( 1 <= segl[ar] - 1 ) itls[++ ils] = Quest ( 1, segl[ar] - 1, 0, 0 );
if ( segr[ar] + 1 <= n ) itls[++ ils] = Quest ( segr[ar] + 1, n, 0, 0 );
}
}
}
void transASsub ( const int l1, const int r1, const int l2, const int r2, const int ID ) {
asq[++ m] = Quest ( r1, r2, ID, 1 ), asq[++ m] = Quest ( r1, l2 - 1, ID, -1 );
asq[++ m] = Quest ( l1 - 1, r2, ID, -1 ), asq[++ m] = Quest ( l1 - 1, l2 - 1, ID, 1 );
}
void transASmany ( const int l, const int r ) {
++ freq;
int ils = 0; splitASdrug ( l, ils );
int aim = ils; splitASdrug ( r, ils );
for ( int i = 1; i <= aim; ++ i ) {
for ( int j = aim + 1; j <= ils; ++ j ) transASsub ( itls[i].l, itls[i].r, itls[j].l, itls[j].r, freq );
}
}
void add1 ( const int x ) { cur += buc2[col[x]], buc1[col[x]] ++; }
void add2 ( const int x ) { cur += buc1[col[x]], buc2[col[x]] ++; }
void sub1 ( const int x ) { cur -= buc2[col[x]], buc1[col[x]] --; }
void sub2 ( const int x ) { cur -= buc1[col[x]], buc2[col[x]] --; }
void captainMO () {
int nowl = 0, nowr = 0;
for ( int i = 1; i <= m; ++ i ) {
for ( ; nowl < asq[i].l; add1 ( ++ nowl ) ) ;
for ( ; nowr < asq[i].r; add2 ( ++ nowr ) ) ;
for ( ; nowl > asq[i].l; sub1 ( nowl -- ) ) ;
for ( ; nowr > asq[i].r; sub2 ( nowr -- ) ) ;
ans[asq[i].ID] += cur * asq[i].x;
}
}
int main () {
n = rint (); int _waste_ = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = pri[i] = rint ();
for ( int i = 1; i < n; ++ i ) {
int u = rint (), v = rint ();
addE ( u, v ), addE ( v, u );
}
initial (), rt = 1;
for ( int i = 1; i <= _waste_; ++ i ) {
int c = rint (), x, y;
if ( c == 1 ) rt = rint ();
else x = rint (), y = rint (), transASmany ( x, y );
}
sort ( asq + 1, asq + 1 + m, existcmp ), captainMO ();
for ( int i = 1; i <= freq; ++ i ) wint ( ans[i] ), putchar ( '\n' );
return 0;
}66. CF1491H Yuezheng Ling and Dynamic Tree
所以 Chinese Round 出 DS 是传统了对吧。
Description
Link.
Given is a rooted tree with the $\sf1$-th node as the root.
The tree will be given in this way: it will tell you that the parent of the $\sf i$-th node is $a_{i}$.
Supporting the following operations:
1 l r x: let $\sf \forall i\in[l,r],a_{i}=max\{a_{i}-x,1\}$.2 u v: find the LCA (Lowest Common Ancestor) of $\sf u$ and $\sf v$.
Solution
经典永流传。
考虑到修改操作是对结点进行的操作，然后这个东西不太能直接 LCT 或树剖，考虑照序列来分块，那么我们来对结点编号分块。
- 修改；
$\quad$维护一个属性 $\sf top_{u}$ 表示在原树上结点 $\sf u$ 的祖先中不和 $\sf u$ 在同一个块里面的编号最大的一个结点的编号，如果不存在的话就令 $\sf top_{u}=1$。这样的话你从结点 $\sf u$ 跳到 root 的复杂度为 $\sf O(\sqrt{n})$。接下来考虑怎么维护这个东西。
$\quad$散块我们直接暴力扫着改；对于整块，可以发现如果一个块的被修改次数超过了块的大小，那么就一定会有 $\sf top_{u}=fa_{u}$。
- 询问。
$\quad$分三个类讨论，这个比较好做（差不多和树剖找 LCA 一个样子）。
#include<bits/stdc++.h>
using namespace std;
int n,m,top[100010],deln[320],tag[320],belong[100010],bl[320],br[320],fa[100010],bs;
#define gtlf(x) ((x-1)*bs+1)
#define gtrg(x) (min(x*bs,n))
void updtop(int x)
{
if(belong[x]^belong[fa[x]]) top[x]=fa[x];
else top[x]=top[fa[x]];
}
void turndown(int x)
{
if(tag[x])
{
for(int i=gtlf(x);i<=gtrg(x);++i) fa[i]=max(fa[i]-tag[x],1);
tag[x]=0;
}
}
int main()
{
scanf("%d %d",&n,&m),bs=sqrt(double(n))+1,fa[1]=belong[1]=1;
for(int i=2;i<=n;++i) scanf("%d",&fa[i]);
for(int i=2;i<=n;++i) belong[i]=(i-1)/bs+1,updtop(i);
while(m--)
{
int opt; scanf("%d",&opt);
if(opt==1)
{
int opl,opr,opx;
scanf("%d %d %d",&opl,&opr,&opx);
turndown(belong[opl]);
if(belong[opl]==belong[opr])
{
turndown(belong[opl]);
for(int i=opl;i<=opr;++i) fa[i]=max(fa[i]-opx,1),updtop(i);
for(int i=opr+1;i<=gtrg(belong[opl]);++i) updtop(i);
}
else
{
turndown(belong[opl]);
for(int i=opl;i<=gtrg(belong[opl]);++i) fa[i]=max(fa[i]-opx,1),updtop(i);
for(int i=gtlf(belong[opl]);i<opl;++i) updtop(i);
turndown(belong[opr]);
for(int i=gtlf(belong[opr]);i<=opr;++i) fa[i]=max(fa[i]-opx,1),updtop(i);
for(int i=opr+1;i<=gtrg(belong[opr]);++i) updtop(i);
for(int i=belong[opl]+1;i<belong[opr];++i)
{
if(deln[i]>=bs) tag[i]+=opx;
else
{
++deln[i];
for(int j=gtlf(i);j<=gtrg(i);++j) fa[j]=max(fa[j]-opx,1),updtop(j);
}
}
}
}
else
{
int opx,opy; scanf("%d %d",&opx,&opy);
while(opx^opy)
{
int fopx,fopy;
if(deln[belong[opx]]>=bs) turndown(belong[opx]),fopx=fa[opx];
else fopx=top[opx];
if(deln[belong[opy]]>=bs) turndown(belong[opy]),fopy=fa[opy];
else fopy=top[opy];
if(belong[opx]^belong[opy])
{
if(belong[opx]>belong[opy]) opx=fopx;
else opy=fopy;
}
else if(fopx^fopy) opx=fopx,opy=fopy;
else
{
if(opx>opy) turndown(belong[opx]),opx=fa[opx];
else turndown(belong[opy]),opy=fa[opy];
}
}
printf("%d\n",opx);
}
}
return 0;
}67. 「NOI2020」时代的眼泪
小 L 喜欢与智者交流讨论，而智者也经常为小 L 出些思考题。
这天智者又为小 L 构思了一个问题。智者首先将时空抽象为了一个二维平面，进而将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。
为了方便，下面记 $(a, b) \leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \leq c, b \leq d$。
更具体地，智者给定了 $n$ 个事件，他们用平面上 $n$ 个不同的点 $\{(x_i, y_i)\}^n_{i=1}$ 来表示；智者还给定了 $m$ 个时代，每个时代用平面上一个矩形 $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ 来表示，其中 $(r_{i,1}, c_{i,1})$ 是矩形的左下角，$(r_{i,2}, c_{i,2})$ 是矩形的右上角，保证 $(r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})$。我们称时代 $i$ 包含了事件 $j$ 当且仅当 $(r_{i,1}, c_{i,1}) \leq (x_j, y_j ) \leq (r_{i,2}, c_{i,2})$。
智者认为若两个事件 $i, j$ 满足 $(x_i, y_i) \leq (x_j, y_j)$，则这两个事件形成了一次遗憾。而对一个时代内包含的所有事件，它们所形成的遗憾被称为这个时代的眼泪，而形成的遗憾次数则称为该时代的眼泪的大小。现在智者想要小 L 计算每个时代的眼泪的大小。
小 L 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。
膜拜 dX。
基本是把 dX 的题解贺了过来所以没啥参考的价值。
不过有很多细节的处理不一样，大概能算个 $\frac{1}{50}$ 成新？
对序列分块，把贡献分成 整块 - 散块 / 整块 - 整块/ 散块 - 整块 / 散块 - 散块 以及 散块内部 / 整块内部 共六种贡献。
记 $\textit{ans}_{0}(l,r,x,y)$ 为询问 $l,r,x,y$ 的答案。
同时预处理出 $\textit{lb}(i,j),\textit{ub}(i,j)$ 分别表示在块 $i$ 中数 $j$ 的 std::lower_bound / std::upper_bound 值，下文如果写成单元函数的形式那么就是省去了第一维。
以及预先做一个块内排序，记为 $\textit{ord}(i,j)$，表示块 $i$ 中排序后的第 $j$ 个元素。
注意本文在每个 subtask 定义的东西在其他 subtask 依然适用。
- 散块 - 散块；
两边的都是 $\sqrt{n}$ 级别，拉出来分别排序后归并计算顺序对即可。
- 散块内部
考虑如何对 $\textit{ans}_{0}(l,r,x,y)$ 进行容斥。
主要矛盾集中在：会出现 $(a\in[1,x),b\in[x,y])$ 这样的贡献。令 $\textit{cnt}_{0}(i,j)$ 表示 $[\textit{lp},i]$ 中 $\textit{rank}_{1}$ 小于 $j$ 的数的数量，其中 $\textit{lp}$ 是当前块的左端点，下同，如果出现 $\textit{rp}$ 同理，$\textit{rank}_{1}$ 的定义见下文。
则容斥可以写为 $\textit{ans}_{0}(l,r,x,y)=\textit{ans}_{0}(l,r,1,y)-\textit{ans}_{0}(l,r,1,x-1)-\sum_{i=l}^{r}[a_{i}\in[x,y]]\cdot\textit{cnt}_{0}(i,\textit{lb}(x)-1)$。
又有 $\textit{ans}_{0}(l,r,1,x)=\sum_{i=l}^{r}[a_{i}\leqslant x]\cdot\textit{cnt}_{0}(i,\textit{rank}_{1}(i))$，我们就可以做到单次 $\mathcal{O}(\sqrt{n})$，注意的 $l,r$ 触及散块边界者不同时，对 $\textit{cnt}_{0}$ 的容斥也有区别。
- 整块 - 整块
令 $\textit{cnt}_{1}(i,j)$ 为块 $[1,i]$ 中 $\leqslant j$ 的元素个数，$\textit{ans}_{1}(L,R,x,y)$ 为块 $[L,R]$ 的答案，以及 $\textit{rank}_{0}(i,j)$ 是块 $i$ 中排名 $j$ 的元素在原数组中的下标。
我们掏出传统容斥：$\textit{ans}_{1}(L,R,x,y)=\textit{ans}_{1}(L,R,1,y)-\textit{ans}_{1}(L,R,1,x-1)-\sum_{i=L}^{R}P_{i}Q_{i}$，$P_{i}$ 是块 $[L,i)$ 中 $<x$ 的元素个数，$Q_{i}$ 是块 $i$ 种 $\in[x,y]$ 的元素个数。
考虑算 $\textit{ans}_{1}(L,R,1,x)$。
定义 $\textit{rank}_{1}(i,j)$ 为块 $i$ 中第 $j$ 个元素的排名（从小到大，下同），$\textit{rank}_{2}(i,j)$ 为块 $i$ 中满足 $<j$ 的最大元素的排名，$\textit{pre}_{b}(i,j)$ 为块 $[i,j]$ 中所有 $<\textit{rank}_{1}(i,j)$ 的元素数量。
易知 $\textit{pre}_{b}(i,j)=\textit{cnt}_{1}(i,\textit{rank}_{1}(i,j)-1)$，再定义 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{0}(i,L,r)}$ 为块 $[1,L]$ 与块 $i$ 前 $r$ 小的元素组成的顺序对数量，同样易知 $\textit{cp}_{0}(i,L,r)=\sum_{k\in T}[\textit{rank}_{1}(i,k)\leqslant r]\cdot\textit{pre}_{b}(L,\textit{rank}_{1}(i,k))$，其中 $T$ 是块 $i$ 的元素集。但这样搞状态数 $\mathcal{O}(n\sqrt{n})$ 转移还要 $\mathcal{\sqrt{n}}$ 而且不好前缀和。
不过可以发现使用 $\textit{ord}$ 数组 $\textit{cp}_{0}$ 就可以递推了：$\textit{cp}_{0}(i,L,r)=\sum_{k=lp}^{r+lp-1}\textit{pre}_{b}(L,k)=\textit{cp}_{0}(i,L,r-1)+\textit{pre}_{b}(L,r+lp-1)$。
然后 $\textit{ans}_{1}(L,R,1,x)=\sum_{i=L+1}^{R}\textit{cp}_{0}(i,i-1,\textit{rank}_{2}(i,x))-\textit{cp}_{0}(i,L-1,\textit{rank}_{2}(i,x))$。
预处理 $\textit{cp}_{0}$ 是 $\mathcal{O}(n\sqrt{n})$，单次回答 $\mathcal{O}(\sqrt{n})$。
- 散块 - 整块
枚举散块里面的元素，利用 $\textit{cnt}_{1}(i,j)$ 计算答案。
具体是令散块元素集为 $T$，整块编号为 $L,R$， $\sum_{i\in T}\textit{cnt}_{1}(R,i)-\textit{cnt}_{1}(L-1,i)$。
- 整块 - 散块
和上面有什么区别吗？
- 整块内部
预处理数组 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{1}(i,x,y)}$ 表示取 $\textit{ord}(i,x\dots y)$ 组成的序列的顺序对数量。
用 $\textit{rank}_{0}$ 来预处理：$\textit{cp}_{1}(i,x,y)=\textit{cp}_{1}(i,x,y-1)+\textit{cnt}_{0}(\textit{rank}_{0}(i,y),y-1)-\textit{cnt}_{0}(\textit{rank}_{0}(i,y),x-1)$。
综上，这个问题得以一个 $\mathcal{O}(n\sqrt{n})$ 的在线算法解决。
//almost copied from dead_X sry
//kouhu has no qiantu
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
int x=0;char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
return x;
}
const int N=101111,A=400,BS=A+10;
ll cp0[BS][BS][BS];
int a[N],rk0[BS][BS],cnt0[N][BS],cp1[BS][BS][BS],lb[BS][N],rk1[N],cnt1[BS][N],L[BS],R[BS];
bool cmp(int x,int y) { return a[x]<a[y]; }
int main(){
#ifdef ONLINE_JUDGE
freopen("tears.in","r",stdin);
freopen("tears.out","w",stdout);
#endif
int n=read(),m=read(),B=n/A;
for(int i=0;i<n;++i)a[i]=read();
for(int i=n;i<(B+1)*A;++i)a[i]=i;
for(int i=0;i<=B;++i){
for(int j=i*A,k=0;k<A;++j,++k)rk0[i][k]=j;
sort(rk0[i],rk0[i]+A,[](int x,int y){return a[x]<a[y];});
for(int j=0;j<A;++j)rk1[rk0[i][j]]=j,cnt0[rk0[i][j]][j]=1;
for(int j=i*A+1;j<(i+1)*A;++j)
for(int k=0;k<A;++k)cnt0[j][k]+=cnt0[j-1][k];
for(int j=i*A;j<(i+1)*A;++j)
for(int k=1;k<A;++k)cnt0[j][k]+=cnt0[j][k-1];
for(int j=i*A;j<(i+1)*A;++j)++cnt1[i][a[j]];
if(i)for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i-1][j];
for(int j=1,k=0;j<=101000;++j)(k<A)&&(j>=a[rk0[i][k]])&&(++k),lb[i][j]=k;
}
for(int i=0;i<=B;++i)
for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i][j-1];
for(int i=1;i<B;++i)for(int j=0;j<i;++j)for(int k=0;k<A;++k)
cp0[i][j][k+1]=cnt1[j][a[rk0[i][k]]]+cp0[i][j][k];
for(int i=0;i<B;++i)for(int j=0;j<A;++j)for(int k=j+1;k<A;++k)
cp1[i][j][k]=cp1[i][j][k-1]+cnt0[rk0[i][k]][k-1]-((j==0)?0:cnt0[rk0[i][k]][j-1]);
for(;m;--m){
int l=read()-1,r=read()-1,x=read(),y=read(),bl=l/A,br=r/A;
if(bl==br){
int ans=0;
for(int i=l;i<=r;++i){
if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[i][rk1[i]-1]-((l%A)?cnt0[l-1][rk1[i]-1]:0);
if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[i][lb[bl][x-1]-1]-((l%A&&lb[bl][x-1])?cnt0[l-1][lb[bl][x-1]-1]:0);
}
printf("%d\n",ans);
}
else{
ll ans=0;
for(int i=l;i<(bl+1)*A;++i){
if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[i][rk1[i]-1]-((l%A)?cnt0[l-1][rk1[i]-1]:0);
if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[i][lb[bl][x-1]-1]-((l%A&&lb[bl][x-1])?cnt0[l-1][lb[bl][x-1]-1]:0);
if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][y]-cnt1[bl][y]-cnt1[br-1][a[i]]+cnt1[bl][a[i]];
}
for(int i=br*A;i<=r;++i){
if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[i][rk1[i]-1];
if(lb[br][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[i][lb[br][x-1]-1];
if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][a[i]]-cnt1[bl][a[i]]-cnt1[br-1][x-1]+cnt1[bl][x-1];
}
int lt=0,rt=0;
for(int i=0;i<A;++i){
if(rk0[bl][i]>=l&&x<=a[rk0[bl][i]]&&a[rk0[bl][i]]<=y)L[++lt]=rk0[bl][i];
if(rk0[br][i]<=r&&x<=a[rk0[br][i]]&&a[rk0[br][i]]<=y)R[++rt]=rk0[br][i];
}
for(int i=1,t=1;i<=rt;++i){
while(t<=lt&&a[L[t]]<a[R[i]])++t;
ans+=t-1;
}
for(int i=bl+1;i<br;++i)if(lb[i][y])ans+=cp1[i][lb[i][x-1]][lb[i][y]-1];
for(int i=bl+2;i<br;++i)
ans+=cp0[i][i-1][lb[i][y]]-cp0[i][bl][lb[i][y]]-cp0[i][i-1][lb[i][x-1]]+cp0[i][bl][lb[i][x-1]],
ans-=ll(cnt1[i][y]-cnt1[i-1][y]-cnt1[i][x-1]+cnt1[i-1][x-1])*(cnt1[i-1][x-1]-cnt1[bl][x-1]);
printf("%lld\n",ans);
}
}
return 0;
}Ds100p -「数据结构百题」51~60
纪念
数据结构一百题50题了呢，该过半周年啦~~~~
LYC和WGY半年的努力让这个几乎玩笑一般的系列到了现在。
今后也请多多关照啦。
祝愿dp100p早日过半
51.CF1000F One Occurrence
给定一个长度为$n$序列，$m$个询问，每次询问给定一个区间$[l,r]$，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出0。$n,m\le 5e5$
题意简述
给定一个序列，每次询问输出一个区间 $[l,r]$ 中只出现一次的数。
题解
这道题其实比较有意思。他让你输出只出现一次的数，讲道理你让我维护个数都还好办，这个就比较好玩了。
我这里给出一种不用吸氧的卡常莫队做法。
其实莫队需要维护的东西很简单，就是一个数的出现次数，我们用一个数组 cnt 来记录。
每次我们算加贡献的时候，cnt 的计算方法很显然。我们同时维护一个栈，算加贡献的时候如果这个数的出现次数为1，我们就把他放到栈顶上去。我们顺手维护一个数组 pos 表示这个数在栈里的位置。
算减贡献的时候 cnt 的计算方法依旧显然。我们把栈顶元素放到删除的数的位置上即可。
每次询问的答案就是栈顶元素，由于不合法的情况输出零，所以没必要特判。
光这样是过不了的，会T飞。
我们需要一个针对于莫队的优化，叫做奇偶性排序优化（瞎编的一个名字），具体来说就是在对询问排序的时候分块的奇偶性，具体实现看代码。这种排序的方式理论来说有 $\Theta(\frac{1}{2})$ 的常数。
这样还是会T。容易发现输出答案的循环可以用unroll循环展开，我设的unroll的参是10，已经能过了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn = 5e5 + 5, Each = 720;
int n, m, top, isa[ Maxn ], cnt[ Maxn ], pos[ Maxn ], htl[ Maxn ], ans[ Maxn ];
struct Query_Node
{
int l, r, id, pos;
Query_Node( int L = 0, int R = 0, int ID = 0 ) { l = L, r = R, id = ID; }
} Q[ Maxn ];
inline int read( )
{
int a = 0, minus = 0;
char ch = getchar( );
while( !isdigit( ch ) )
{
if( ch == '-' ) minus = 1;
ch = getchar( );
}
while( isdigit( ch ) )
{
a = a * 10 + ch - '0';
ch = getchar( );
}
if( minus ) return -a;
else return a;
}
inline void write( int x )
{
if( x < 0 )
{
x = -x;
putchar( '-' );
}
if( x > 9 ) write( x / 10 );
putchar( x % 10 + '0' );
}
inline bool cmp( Query_Node rhs, Query_Node shr )
{
if( rhs.pos != shr.pos ) return rhs.l < shr.l;
else if( rhs.pos & 1 ) return rhs.r < shr.r;
else return rhs.r > shr.r;
}
inline void Make_Cont( int x, int t )
{
x = isa[ x ];
if( t == 1 ) ++ cnt[ x ];
else --cnt[ x ];
if( cnt[ x ] == 1 )
{
htl[ ++ top ] = x;
pos[ x ] = top;
}
else if( ( t == 1 ) ? ( cnt[ x ] == 2 ) : ( cnt[ x ] == 0 ) )
{
htl[ pos[ x ] ] = htl[ top ];
pos[ htl[ top ] ] = pos[ x ];
pos[ x ] = htl[ top -- ] = 0;
}
}
inline void Contribute( )
{
int l = 1, r = 0;
for( int i = 0; i < m; ++ i )
{
while( l < Q[ i ].l ) Make_Cont( l ++, 0 );
while( l > Q[ i ].l ) Make_Cont( -- l, 1 );
while( r < Q[ i ].r ) Make_Cont( ++ r, 1 );
while( r > Q[ i ].r ) Make_Cont( r --, 0 );
ans[ Q[ i ].id ] = htl[ top ];
}
}
signed main( )
{
n = read( );
for( int i = 1; i <= n; ++ i ) isa[ i ] = read( );
m = read( );
for( int i = 0; i < m; ++ i )
{
Q[ i ].l = read( );
Q[ i ].r = read( );
Q[ i ].id = i;
Q[ i ].pos = Q[ i ].l / Each;
}
sort( Q, Q + m, cmp );
Contribute( );
if( m <= 10 )
{
for( int i = 0; i < m; ++ i ) write( ans[ i ] ), putchar( '\n' );
return 0;
}
#pragma unroll 10
for( int i = 0; i < m; ++ i ) write( ans[ i ] ), putchar( '\n' );
return 0;
}52.P5046 [Ynoi2019模拟赛]Yuno loves sqrt technology I
给你一个长为 $n$ 的排列，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。
题意简述
无修改区间求逆序对。
题解
首先有一个显然的 $\Theta(N\sqrt{N}\log_{2}N)$ 做法，由于过不了所以我就不废话。
其实有了 $\Theta(N\sqrt{N}\log_{2}N)$ 的过不去做法，我们就可以根据这个思路然后预处理解决问题。
我们需要处理的信息有：
- 散块的逆序对数量
- 以块为单位的区间逆序对数量
那么我们需要处理的数组就有以下几个：
previous[i]表示 $i$ 到 该块开头的逆序对数量。suffix[i]同理。block[i][j]表示前 $i$ 个块中 $\leq j$ 元素个数。intervals[i][j]表示以块为单位的区间 $[i,j]$ 中的逆序对数量。
讲讲预处理方法。
previous[i]和suffix[i]的处理方法都很显然，可以一直扫着然后FWT扫就行。block[i][j]可以递推，递推式为block[i][j]=block[i+1][j]+block[i][j-1]-block[i+1][j-1]+cont(i,j)。其中cont(i,j)表示计算对应块的逆序对数。intervals[i][j]每次循环到块的开头继承上一个块的贡献即可。
计算贡献的方法很简单，归并即可。mrsrz讲得也挺清楚的，我这里就不再赘述，主要讲讲怎么卡常。
首先我们可以把主函数里的所有循环全部展开，经过实践参数传8的时候跑得比较快。
然后八聚氧先加上，luogu O2也开着。
再其次快读fread快输fwrite，这些都是卡常的标配。
然后就把能拿出来的结构体拿出来，实在不能就不管了。
然后去STL，pair vector能去就去。
然后long long开在正确的地方，不要无脑replace。
函数inline，循环register。虽然可能作用不大但是可以先加上。
然后调块长，经过无数次实践发现取150~170较为优秀。
然后加了过后发现就算rp再好也只有60pts。
然后谷歌搜索硫酸的化学式H₂SO₄，给评测机喂硫酸（idea来自SyadouHayami）。
然后本来交了5页都过不了，这下再交两次就过了。
// 省略八聚氧
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Maxn = 1e5 + 5;
const int Maxm = 650;
const int each = 160;
int n, m, blocks, Lp[Maxn], Rp[Maxn], isa[Maxn], head[Maxn], tail[Maxn], sorted[Maxn], belong[Maxn], previous[Maxn], suffix[Maxn], block[Maxm][Maxn];
long long intervals[Maxm][Maxn];
struct Holy_Pair
{
int first, second;
bool operator < (const Holy_Pair& rhs) const
{
return first < rhs.first;
}
} current[Maxn];
struct Fenwick_Tree
{
int fwt[Maxn];
inline void Modify(int x, int v)
{
for (; x + 5 <= Maxn; x += x & -x) fwt[x] += v;
}
inline int Query(int x)
{
int ret = 0;
for (; x; x ^= x & -x) ret += fwt[x];
return ret;
}
} FWT;
#define io_e '\0'
#define io_s ' '
#define io_l '\n'
namespace Fast_IO
{
... // 省略快读
} // namespace Fast_IO
using Fast_IO::read;
using Fast_IO::write;
inline Holy_Pair make_pair(int first, int second)
{
Holy_Pair ret;
ret.first = first;
ret.second = second;
return ret;
}
inline int Merge_Vct(int rhs[], int shr[], int szl, int szr)
{
int itl = 1, itr = 1;
int ret = 0, ctr = 1;
while (itl <= szl && itr <= szr)
{
if (rhs[itl] < shr[itr]) ++itl, ++ctr;
else
{
ret += szl - ctr + 1;
++itr;
}
}
return ret + szr - szr;
}
inline int Merge_Idx(int st1, int st2, int sz1, int sz2)
{
int ret = 0, id1 = st1 + 1, id2 = st2 + 1;
sz1 += st1, sz2 += st2;
while (id1 <= sz1 && id2 <= sz2)
{
if (sorted[id1] < sorted[id2]) ++id1;
else
{
ret += sz1 - id1 + 1;
++id2;
}
}
return ret;
}
inline void Behavior(int l, int r, long long &ans)
{
int itl = 0, itr = 0;
if (belong[l] == belong[r])
{
for (int i = head[belong[l]]; i <= tail[belong[r]]; ++i)
{
if (current[i].second >= l && current[i].second <= r) Rp[++itr] = sorted[i];
else if (current[i].second < l) Lp[++itl] = sorted[i];
}
if (l == head[belong[l]]) ans = previous[r] - Merge_Vct(Lp, Rp, itl, itr);
else ans = previous[r] - previous[l - 1] - Merge_Vct(Lp, Rp, itl, itr);
}
else
{
ans = intervals[belong[l] + 1][belong[r] - 1] + previous[r] + suffix[l];
for (int i = head[belong[l]]; i <= tail[belong[l]]; ++i)
{
if (current[i].second >= l)
{
Lp[++itl] = sorted[i];
ans += block[belong[r] - 1][1] - block[belong[r] - 1][sorted[i]] - block[belong[l]][1] + block[belong[l]][sorted[i]];
}
}
for (int i = head[belong[r]]; i <= tail[belong[r]]; ++i)
{
if (current[i].second <= r)
{
Rp[++itr] = sorted[i];
ans += block[belong[r] - 1][sorted[i] + 1] - block[belong[l]][sorted[i] + 1];
}
}
ans += Merge_Vct(Lp, Rp, itl, itr);
}
write(io_l, ans);
}
signed main()
{
read(n, m), blocks = (n - 1) / each + 1;
if (n <= 8)
{
for (int i = 1; i <= n; ++i)
{
read(isa[i]);
current[i] = make_pair(isa[i], i);
}
}
else
{
#pragma unroll 8
for (int i = 1; i <= n; ++i)
{
read(isa[i]);
current[i] = make_pair(isa[i], i);
}
}
if (blocks <= 8)
{
for (int i = 1; i <= blocks; ++i)
{
head[i] = tail[i - 1] + 1;
tail[i] = tail[i - 1] + each;
if (i == blocks) tail[i] = n;
}
}
else
{
#pragma unroll 8
for (int i = 1; i <= blocks; ++i)
{
head[i] = tail[i - 1] + 1;
tail[i] = tail[i - 1] + each;
if (i == blocks) tail[i] = n;
}
}
if (blocks <= 8)
{
for (int i = 1; i <= blocks; ++i)
{
memcpy(block[i], block[i - 1], sizeof(block[0]));
sort(current + head[i], current + 1 + tail[i]);
for (int j = head[i]; j <= tail[i]; ++j)
{
++block[i][isa[j]];
belong[j] = i;
sorted[j] = current[j].first;
}
int satisfy = 0;
for (int j = head[i]; j <= tail[i]; ++j)
{
FWT.Modify(isa[j], 1);
satisfy += FWT.Query(n) - FWT.Query(isa[j]);
previous[j] = satisfy;
}
intervals[i][i] = satisfy;
for (int j = head[i]; j <= tail[i]; ++j)
{
suffix[j] = satisfy;
FWT.Modify(isa[j], -1);
satisfy -= FWT.Query(isa[j] - 1);
}
}
}
else
{
#pragma unroll 8
for (int i = 1; i <= blocks; ++i)
{
memcpy(block[i], block[i - 1], sizeof(block[0]));
sort(current + head[i], current + 1 + tail[i]);
for (int j = head[i]; j <= tail[i]; ++j)
{
++block[i][isa[j]];
belong[j] = i;
sorted[j] = current[j].first;
}
int satisfy = 0;
for (int j = head[i]; j <= tail[i]; ++j)
{
FWT.Modify(isa[j], 1);
satisfy += FWT.Query(n) - FWT.Query(isa[j]);
previous[j] = satisfy;
}
intervals[i][i] = satisfy;
for (int j = head[i]; j <= tail[i]; ++j)
{
suffix[j] = satisfy;
FWT.Modify(isa[j], -1);
satisfy -= FWT.Query(isa[j] - 1);
}
}
}
if (blocks <= 8)
{
for (int dis = 1; dis <= blocks; ++dis)
{
for (int i = n - 1; i; --i) block[dis][i] += block[dis][i + 1];
for (int l = 1, r = dis + 1; r <= blocks + 1; ++l, ++r)
intervals[l][r] = intervals[l + 1][r] + intervals[l][r - 1] - intervals[l + 1][r - 1] +
Merge_Idx(head[l] - 1, head[r] - 1, tail[l] - head[l] + 1, tail[r] - head[r] + 1);
}
}
else
{
#pragma unroll 8
for (int dis = 1; dis <= blocks; ++dis)
{
for (int i = n - 1; i; --i) block[dis][i] += block[dis][i + 1];
for (int l = 1, r = dis + 1; r <= blocks + 1; ++l, ++r)
intervals[l][r] = intervals[l + 1][r] + intervals[l][r - 1] - intervals[l + 1][r - 1] +
Merge_Idx(head[l] - 1, head[r] - 1, tail[l] - head[l] + 1, tail[r] - head[r] + 1);
}
}
if (m <= 8)
{
long long lastans = 0;
for (int i = 0; i < m; ++i)
{
long long l, r;
read(l, r);
l ^= lastans;
r ^= lastans;
Behavior(l, r, lastans);
}
}
else
{
long long lastans = 0;
#pragma unroll 8
for (int i = 0; i < m; ++i)
{
long long l, r;
read(l, r);
l ^= lastans;
r ^= lastans;
Behavior(l, r, lastans);
}
}
return 0;
}53.SP20644 ZQUERY - Zero Query
长度为$n$的序列，序列中的值为$1$或$-1$
有$m$个询问，询问在$[L,R]$中区间和为$0$的区间的最大长度
题意简述
求区间中区间和为0的最长区间。
题解
首先前缀和基本操作，然后问题转化为：
给定询问区间 $[l,r]$，求区间中相同的数的最远间隔距离，即P5906。
考虑莫队来整。
可以维护两个东西，一个是 pre[x] 表示当前的询问区间 $[l,r]$ 中 $x$ 最早出现的位置。
还有一个是 suf[x] 表示当前的询问区间 $[l,r]$ 中 $x$ 最后出现的位置。
在莫队加贡献的时候这些很好整，分别像这样维护：
如果加贡献时出现了数 $x$ 那么 pre[x]=p，$p$ 表示加贡献时计算的位置。
suf[x] 同理。
那么询问的答案就是 $\max_{i\in [l,r]}\{suf_{a_{x}}-pre_{a_{x}}\}$。
中间有个特殊情况就是需要判断还没被更新过的时候，自己打代码的时候注意点。
然后发现一个神奇的事情：减贡献我们做不来了！
既然我们不会做减法，那就不做吧。
正常的莫队的询问区间左右指针 $l,r$ 一般初值为 $l=1,r=0$。
我们这里换一种方式。
首先我们把询问分块，然后排序，这是莫队的常规操作。
然后再枚举每个块，我们首先处理询问的左端点在当前块中的询问，思考一下询问分块的排序方式就可以知道这种算法的正确性。
然后我们把指针的初值设为 $l=R_{i}+1,r=R_{i}-1$，其中数组 $R$ 表示块的左端点。
然后如果询问区间在一个块中就暴力。
由于询问区间在一个块中的询问我们已经暴力处理过了，所以剩下的询问右端点一定在其他块。
然后 $r$ 指针正常右移，这一步只需要加贡献。
所以 $l$ 指针只需要左移，我们就可以合并两次的贡献，就是这次询问的答案。
由于排序的规则，剩下的询问右端点一定在当前询问右端点的右边，所以我们的 $r$ 指针可以不用管，就放到当前询问的位置。
但是 $l$ 是无序的，所以我们需要撤销计算 $l$ 产生的贡献，这很简单，不赘述。
这种算法叫回滚莫队。
但是这种trick我在之前一道莫队题中想到过，不过觉得太麻烦就没打。
后来发现有这个东西的板子，又重学了一遍。
还是挺好玩的吧，数据结构。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int Maxn = 2e5 + 5;
int n, m, each, cube, isa[Maxn], pre[Maxn], nxt[Maxn], vio[Maxn], ans[Maxn], bel[Maxn], head[Maxn], tail[Maxn];
struct Query_Node
{
int l, r, id;
} Q[Maxn];
bool cmp(Query_Node rhs, Query_Node shr)
{
if (bel[rhs.l] == bel[shr.l]) return rhs.r < shr.r;
else return bel[rhs.l] < bel[shr.l];
}
void Contribute(int las = 0)
{
for (int k = 1; k <= cube; ++k)
{
int l = tail[k] + 1, r = tail[k], ret = 0;
vector < int > vctr;
for (int c = las + 1; bel[Q[c].l] == k; ++c)
{
int ql = Q[c].l, qr = Q[c].r, now = 0;
if (bel[ql] == bel[qr])
{
for (int i = ql; i <= qr; ++i) vio[isa[i]] = 0;
for (int i = ql; i <= qr; ++i)
{
if (!vio[isa[i]]) vio[isa[i]] = i;
else now = max(now, i - vio[isa[i]]);
}
ans[Q[c].id] = now;
las = c;
}
else
{
while (r < qr)
{
++r;
nxt[isa[r]] = r;
if (pre[isa[r]] == 0)
{
pre[isa[r]] = r;
vctr.push_back(isa[r]);
}
ret = max(ret, nxt[isa[r]] - pre[isa[r]]);
}
now = ret;
while (l > ql)
{
--l;
if (nxt[isa[l]] == 0) nxt[isa[l]] = l;
else ret = max(ret, nxt[isa[l]] - l);
}
while (l < tail[k] + 1)
{
if (nxt[isa[l]] == l) nxt[isa[l]] = 0;
++l;
}
ans[Q[c].id] = ret;
ret = now;
las = c;
}
}
for (unsigned i = 0; i < vctr.size(); ++i) pre[vctr[i]] = nxt[vctr[i]] = 0;
}
}
signed main()
{
scanf("%d %d", &n, &m);
++n;
each = pow(n, 0.5);
cube = (n - 1) / each + 1;
for (int i = 2; i <= n; ++i)
{
scanf("%d", &isa[i]);
isa[i] += isa[i - 1];
}
for (int i = 1; i <= n; ++i) isa[i] += 50005;
for (int i = 1; i <= cube; ++i)
{
head[i] = tail[i - 1] + 1;
tail[i] = tail[i - 1] + each;
for (int j = head[i]; j <= tail[i]; ++j) bel[j] = i;
if (i == cube) tail[i] = n;
}
for (int i = 1; i <= m; ++i)
{
scanf("%d %d", &Q[i].l, &Q[i].r);
Q[i].r += 1;
Q[i].id = i;
}
sort(Q + 1, Q + 1 + m, cmp);
Contribute();
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}54.P5268 [SNOI2017]一个简单的询问
给你一个长度为 $N$ 的序列 $a_i$，$1\leq i\leq N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出
$$ \sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x) $$
$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。
题意简述
求式子
题解
纯算式子nt行为，由于是出现次数，满足区间加减性，所以我们可以这样表达 $\mathrm{get}(l,r,x)$（省略 $x$）:
$$ \mathrm{get}(l,r)=\mathrm{get}(1,r)-\mathrm{get}(1,l-1) $$
那么我们代进原式，化一波式子：
$$ \sum_{i=1}^{\infty}\mathrm{get}(l_{1},r_{1},x)\times\mathrm{get}(l_{2},r_{2},x) $$
$$ \sum_{i=1}^{\infty}(\mathrm{get}(1,r_{1})-\mathrm{get}(1,l_{1}-1))\times(\mathrm{get}(1,r_{2})-\mathrm{get}(1,l_{2}-1)) $$
$$ \sum_{i=1}^{\infty}\mathrm{get}(r_{1})\times\mathrm{get}(r_{2})-\mathrm{get}(r_{1})\times\mathrm{get}(l_{2}-1)-\mathrm{get}(l_{1}-1)\times\mathrm{get}(r_{2})+\mathrm{get}(l_{1}-1))\times\mathrm{get}(l_{2}-1) $$
$$ \mathrm{let}\ F(x,y)=\sum_{d}\mathrm{get}(1,l,d)\times\mathrm{get}(1,r,d) $$
则答案为:
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
考虑怎么更新，比如从 $l$ 更新到 $l+1$，则：
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l+1)}\times\mathrm{get}(1,r) $$
$$ \mathrm{get(1,l)}\times\mathrm{get}(1,r)+\mathrm{cont}(a_{l}) $$
其中 $\mathrm{cont}(a_{l})$ 表示 $a_{l}$ 的出现次数。
则我们就知道怎么更新了，由于我们维护和的是前缀信息，所以姿势和普通莫队有点不一样。
维护两个数组 cntl[x] 和 cntr[y] 表示答案式子
$$ F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1) $$
中 $F(x,y)$ 的值。
式子和表达可能有些玄学，自己意会一下吧。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn = 50000 + 5;
int n, m, q, each, cube, isa[Maxn], bel[Maxn], cntl[Maxn], cntr[Maxn];
long long now, ans[Maxn];
struct Query_Node
{
int l, r, id, typ;
Query_Node(int tl = 0, int tr = 0, int tid = 0, int tpyt = 0)
{
l = tl;
r = tr;
id = tid;
typ = tpyt;
}
} Q[Maxn << 2];
bool cmp(Query_Node rhs, Query_Node shr)
{
if (bel[rhs.l] == bel[shr.l]) return rhs.r < shr.r;
else return rhs.l < shr.l;
}
void Contribute()
{
int l = 0, r = 0;
for (int i = 1; i <= m; ++i)
{
while (l < Q[i].l)
{
++cntl[isa[++l]];
now += cntr[isa[l]];
}
while (l > Q[i].l)
{
--cntl[isa[l]];
now -= cntr[isa[l--]];
}
while (r < Q[i].r)
{
++cntr[isa[++r]];
now += cntl[isa[r]];
}
while (r > Q[i].r)
{
--cntr[isa[r]];
now -= cntl[isa[r--]];
}
ans[Q[i].id] += Q[i].typ * now;
}
}
signed main()
{
scanf("%d", &n);
each = 230;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &isa[i]);
bel[i] = (i - 1) / each + 1;
}
scanf("%d", &q);
for (int i = 1; i <= q; ++i)
{
int l1, r1, l2, r2;
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
Q[++m] = Query_Node(r1, r2, i, 1);
Q[++m] = Query_Node(r1, l2 - 1, i, -1);
Q[++m] = Query_Node(l1 - 1, r2, i, -1);
Q[++m] = Query_Node(l1 - 1, l2 - 1, i, 1);
}
for (int i = 1; i <= m; ++i)
{
if (Q[i].l < Q[i].r) swap(Q[i].l, Q[i].r);
}
sort(Q + 1, Q + 1 + m, cmp);
Contribute();
for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}55.P3466 [POI2008]KLO-Building blocks
有 $n$ 柱砖,每柱砖有一个高度，我们现在希望有连续 $k$ 柱的高度是一样的。
你可以选择以下两个动作：
1:从某柱砖的顶端拿一块砖出来,丢掉不要了。
2:从仓库中拿出一块砖,放到另一柱，仓库是无限大的。
现在希望用最小次数的动作完成任务，除此之外你还要求输出结束状态时,每柱砖的高度。
题意简述
给定一个长度为 $n$ 的序列，支持单点减一，单点加法的操作，问把一个长度为 $k$ 的区间里的值变成同样的最小操作数。
题解
挺好的一道平衡树练手+猜结论题。（雾
化简一下题意，我们需要找到一个值 $m$ 且 $m$ 使得 $\sum_{i=1}^{r}\mid a_{i}-x\mid$ 最小。
其中 $r-l+1=k$。
大约可以猜到这里需要取中位数。
感性理解一下，把 $a_{l},a_{l+1},\cdots,a_{r}$ 排序后如果每个数要取最小只能取中位数。
可以当成一个结论式的东西积累起来。
那么我们就需要一个数据结构，支持插入，删除，查 $k_{th}$。
这里我选择的是Zip-Tree，也就是国内常说的FHQ-Treap。
具体的做法是，枚举每个长度为 $k$ 的区间 $[l,r]$，首先我们把 $a_{1},a_{2},\cdots,a_{k}$ 插入平衡树，然后根据 $k$ 的奇偶性用 $k_{th}$ 操作找到中位数（序列的中位数根据序列的长度奇偶性不同有区别）。
然后计算贡献即可，顺手记录一下区间的位置，方便输出答案。
贡献的计算可以分成大于中位数，小于中位数，等于中位数的情况。
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <climits>
#define int long long
const int Maxn = 1e5 + 5;
int n, k, rt, tot, isa[Maxn];
struct Treap
{
int l, r, siz, sum, key, val;
} t[Maxn];
int newnode(int val)
{
t[++tot].val = val;
t[tot].sum = val;
t[tot].key = rand();
t[tot].siz = 1;
return tot;
}
void maintain(int x)
{
t[x].siz = t[t[x].l].siz + t[t[x].r].siz + 1;
t[x].sum = t[t[x].l].sum + t[t[x].r].sum + t[x].val;
}
void Split(int now, int val, int &x, int &y)
{
if (now == 0) x = y = 0;
else
{
if (val >= t[now].val)
{
x = now;
Split(t[now].r, val, t[now].r, y);
}
else
{
y = now;
Split(t[now].l, val, x, t[now].l);
}
maintain(now);
}
}
int Merge(int x, int y)
{
if (x == 0 || y == 0) return x + y;
else
{
if (t[x].key > t[y].key)
{
t[x].r = Merge(t[x].r, y);
maintain(x);
return x;
}
else
{
t[y].l = Merge(x, t[y].l);
maintain(y);
return y;
}
}
}
int rt1, rt2, rt3;
void Insert(int val)
{
Split(rt, val, rt1, rt2);
rt = Merge(rt1, Merge(newnode(val), rt2));
}
void Remove(int val)
{
Split(rt, val, rt1, rt3);
Split(rt1, val - 1, rt1, rt2);
rt2 = Merge(t[rt2].l, t[rt2].r);
rt = Merge(rt1, Merge(rt2, rt3));
}
int Find_Kth(int rnk)
{
int now = rt;
while (now)
{
if (t[t[now].l].siz + 1 == rnk) break;
else if (t[t[now].l].siz >= rnk) now = t[now].l;
else
{
rnk -= t[t[now].l].siz + 1;
now = t[now].r;
}
}
return t[now].val;
}
int Query(int mid)
{
Split(rt, mid, rt1, rt3);
Split(rt1, mid - 1, rt1, rt2);
int lth = rt1, mth = rt3;
int cont_l = t[lth].siz * mid - t[lth].sum;
int cont_r = t[mth].sum - t[mth].siz * mid;
rt = Merge(rt1, Merge(rt2, rt3));
return cont_l + cont_r;
}
signed main()
{
srand((unsigned)(time(NULL)));
int MID, LEFT, RIGHT, ANS = LONG_LONG_MAX;
scanf("%lld %lld", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%lld", &isa[i]);
for (int i = 1; i <= k; ++i) Insert(isa[i]);
int l = 1, r = k;
for (int i = k; i <= n; ++i)
{
int mid;
if (k & 1) mid = Find_Kth((k >> 1) + 1);
else mid = (Find_Kth(k >> 1) + Find_Kth((k >> 1) + 1)) >> 1;
int xxx = Query(mid);
if (ANS > xxx)
{
ANS = xxx;
MID = mid;
LEFT = l - 1;
RIGHT = r + 1;
}
l++, r++;
Remove(isa[l - 1]);
Insert(isa[r]);
}
printf("%lld\n", ANS);
for (int i = 1; i <= LEFT; ++i) printf("%lld\n", isa[i]);
for (int i = LEFT + 1; i <= RIGHT - 1; ++i) printf("%lld\n", MID);
for (int i = RIGHT; i <= n; ++i) printf("%lld\n", isa[i]);
return 0;
}56.P5610 [Ynoi2013]大学
一个长为 $n$ 的非负整数序列 $a$，支持以下两个操作：
1 l r x：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。2 l r：查询区间 $[l,r]$ 的和。
本题强制在线，每次的 $l,r,x$ 需要 xor 上上次答案，如果之前没有询问，则上次答案为 $0$。
题意简述
区间查 $x$ 的倍数并除掉，区间查和。
题解
平衡树。
首先有个基本的想法就是按 $a_{i}$ 开平衡树，即对于每个 $a_{i}$ 都开一棵平衡树，共5e5棵，第 $i$ 棵平衡树维护的值是所有 $a_{i}$ 的倍数在原数组中的下标，用处后面讲。
注意到一个小性质，一个正整数 $A$ 最多被整除 $\log_{2}A$ 次，这个很好想，每次都至少减少一半。可以当成一个 trick 记下来。
整个区间的数最多被除 $\sum_{i=1}^{n}\log_{2}a_{i}$ 次，区间和的操作可以用树状数组操作实现，则整体的操作复杂度为 $\Theta(\sum_{i=1}^{n}\log_{2}a_{i}+\log_{2}a_{i})$。
开头提到了对于每个 $a_{i}$ 我们都开一棵平衡树，作用就体现在这里。因为如果要保证正确的时间复杂度，我们需要快速的找到需要执行操作的数。
这里我采用的是 FHQ-Treap。
我们可以用两次 split 操作在 $x$ 的平衡树中提取出当前的询问区间，由于我们是以下标为平衡树维护的权值，所以我们用按值分裂即可提取出区间。
然后我们就在提取出的子树中 DFS 遍历，然后暴力操作，把操作后依然是 $x$ 的倍数的数记录下来，操作完后用这个数组再建一棵临时树然后和之前 split 出来的子树一起合并回去。
【记得配图，解释一下】
操作之前记得预处理每个数的所有约数，这个简单，直接用 vector 即可。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;
typedef long long t_t;
const int Maxn = 1e5 + 5;
const int Maxa = 5e5 + 5;
int n, m, xxx, zip, tot, isa[Maxn], bin[Maxa], root[Maxa];
struct Treap
{
int l, r, key, val;
} t[Maxa * 230];
struct Fenwick_Tree
{
t_t bit[Maxn];
void ins(int x, t_t v)
{
for (; x <= n; x += x & -x) bit[x] += v;
}
t_t sum(int x)
{
t_t ret = 0;
for (; x; x -= x & -x) ret += bit[x];
return ret;
}
} fwt;
vector < int > vec[Maxa];
int newnode(int val)
{
t[++tot].val = val;
t[tot].key = rand();
return tot;
}
void split(int now, int val, int &x, int &y)
{
if (now == 0) x = y = 0;
else
{
if (t[now].val <= val)
{
x = now;
split(t[now].r, val, t[now].r, y);
}
else
{
y = now;
split(t[now].l, val, x, t[now].l);
}
}
}
int merge(int x, int y)
{
if (x == 0 || y == 0) return x | y;
if (t[x].key > t[y].key)
{
t[x].r = merge(t[x].r, y);
return x;
}
else
{
t[y].l = merge(x, t[y].l);
return y;
}
}
int build(int l, int r)
{
if (l > r) return 0;
int mid = (l + r) >> 1;
int now = newnode(bin[mid]);
t[now].l = build(l, mid - 1);
t[now].r = build(mid + 1, r);
return now;
}
void dfs(int now, int val)
{
if (now == 0) return ;
dfs(t[now].l, val);
if (isa[t[now].val] % val == 0)
{
fwt.ins(t[now].val, -isa[t[now].val]);
isa[t[now].val] /= val;
fwt.ins(t[now].val, isa[t[now].val]);
}
if (isa[t[now].val] % val == 0) bin[++zip] = t[now].val;
dfs(t[now].r, val);
}
int tx, ty, tp;
void change(int l, int r, int x)
{
if (x == 1) return ;
split(root[x], r, tx, tp);
split(tx, l - 1, tx, ty);
zip = 0;
dfs(ty, x);
root[x] = merge(tx, merge(build(1, zip), tp));
}
signed main()
{
srand((114514 - 1) / 3 - 4);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &isa[i]);
fwt.ins(i, isa[i]);
xxx = max(xxx, isa[i]);
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j * j <= isa[i]; ++j)
{
if (isa[i] % j == 0)
{
vec[j].push_back(i);
if (j * j != isa[i]) vec[isa[i] / j].push_back(i);
}
}
}
for (int i = 1; i <= xxx; ++i)
{
zip = 0;
for (unsigned j = 0; j < vec[i].size(); ++j) bin[++zip] = vec[i][j];
root[i] = build(1, zip);
}
for (int i = 0; i < m; ++i)
{
int t, l, r, x;
scanf("%d %d %d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &x);
change(l, r, x);
}
else printf("%lld\n", fwt.sum(r) - fwt.sum(l - 1));
}
return 0;
}57.CF803G Periodic RMQ Problem
给你一个序列$a$ 让你支持
$1$ $l$ $r$ $x$ 区间赋值
$2$ $l$ $r$ 询问区间最小值
我们觉得这个问题太水了,所以我们不会给你序列$a$
而是给你序列一个长度为$n$ 的序列$b$ ,把$b$ 复制粘贴$k$ 次就可以得到$a$
$n\le10^5,k\le10^4,q\le10^5,b_i\le10^9$
$1\le l\le r\le n\times k$
题目解释：
有一个由给定序列不断首尾拼接而成的序列（很长，存不下）。
要求实现两个操作：区间赋值和查询区间最小值。
这个序列很长不好操作，所以我们要进行离散化，缩小一下操作的范围。
把每个操作的左端点减一和右端点加入离散化数组$pri$（这里下标从1开始）。
离散化后第i个块的左端点是$pri[i-1]+1$,右端点是$pri[i]$。（离散化还要插入$0$和最后一个位置的下标，不然有些位置没有被覆盖到）
但是离散化之后我们不知道每个离散化出来的块内的最小值，这样就无法初始化。
我们可以利用之前给出用来首尾拼接的序列求出来。
对每个块分类讨论：（设给定用来拼接的序列长为$n$）
1).块长大于等于$n$：
此时这个块已经覆盖了整个给定序列，那它的最小值直接就是给定序列的最小值。
2).块长小于$n$：
又要分两种情况:
$\ \ \ \ $A).左端点投射到序列中的位置在右端点的后面（由于是由同一序列首尾拼接而成，我们可以把它们投射到一个序列上）。
$\ \ \ \ $就是说：这个块覆盖的给定序列的前面的一部分和后面的一部分。
$\ \ \ \ $就像这样：
$\ \ \ \ $投射到给定序列上就像这样：
$\ \ \ \ $那么我们直接查询（涂色的）这两段的最小值再取个$min$就好了。
$\ \ \ \ $其实就是从他们中间的序列尾（就是更上面的那张图L,R中间那条黑线）分开来求两边的最小值再取$min$，就得到了他们之间的最小值。
$\ \ \ \ $B).左端点投射到序列中的位置在右端点的前面。
$\ \ \ \ $仿照上个情况，投射到序列上查询他们之间的最小值即可。
由于是以操作的左右端点做的离散化，所以一个块内要么一起被询问，要么一起被修改。
所以我们用上面的方法处理出这个离散化后的序列每个块的初始值之后，就可以用线段树把它当板题做了！
代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> pri;
const int INF=1e9+1;
int n,q,k,a[100010],ori[400010],op[100010],opl[100010],opr[100010],opx[100010],nodes[1000010],tag[2000010],s;
void buildori(int l,int r,int x)//对于给定序列的线段树建树。
{
if(l^r)
{
int mid=(l+r)>>1;
buildori(l,mid,x<<1);
buildori(mid+1,r,x<<1|1);
ori[x]=min(ori[x<<1],ori[x<<1|1]);
}
else ori[x]=a[l];
}
int findori(int l,int r,int x,int fr,int ba)//查询给定序列里的区间最小值。
{
if(l>ba||r<fr) return INF;
if(l>=fr&&r<=ba) return ori[x];
else
{
int mid=(l+r)>>1;
return min(findori(l,mid,x<<1,fr,ba),findori(mid+1,r,x<<1|1,fr,ba));
}
}
void build(int l,int r,int x)//对离散化后的序列建树。
{
if(l^r)
{
int mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
nodes[x]=min(nodes[x<<1],nodes[x<<1|1]);
}
else
{
if(pri[l]-pri[l-1]>=n) nodes[x]=ori[1];//情况1).
else
{
int one=(pri[l-1]+1)%n;
if(one==0) one=n;
int two=pri[l]%n;
if(two==0) two=n;
if(one>two) nodes[x]=min(findori(1,n,1,one,n),findori(1,n,1,1,two));//情况2).A).
else nodes[x]=findori(1,n,1,one,two);//情况2).B).
}
}
}
//后面的就是模板操作。
void pushdown(int x)
{
if(tag[x])
{
nodes[x]=tag[x];
tag[x<<1]=tag[x<<1|1]=tag[x];
tag[x]=0;
}
}
void update(int l,int r,int x,int fr,int ba,int val)
{
if(l>ba||r<fr) return;
if(l>=fr&&r<=ba) tag[x]=val;
else
{
int mid=(l+r)>>1;
pushdown(x);
update(l,mid,x<<1,fr,ba,val);
update(mid+1,r,x<<1|1,fr,ba,val);
pushdown(x<<1);
pushdown(x<<1|1);
nodes[x]=min(nodes[x<<1],nodes[x<<1|1]);
}
}
int find(int l,int r,int x,int fr,int ba)
{
if(l>ba||r<fr) return INF;
pushdown(x);
if(l>=fr&&r<=ba) return nodes[x];
else
{
int mid=(l+r)>>1;
return min(find(l,mid,x<<1,fr,ba),find(mid+1,r,x<<1|1,fr,ba));
}
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
buildori(1,n,1);
scanf("%d",&q);
pri.push_back(0);
pri.push_back(n*k);//插入0和最后一个位置的下标。
for(int i=1;i<=q;++i)
{
scanf("%d %d %d",&op[i],&opl[i],&opr[i]);
if(op[i]==1) scanf("%d",&opx[i]);
pri.push_back(opl[i]-1);
pri.push_back(opr[i]);//把每个操作的左端点减一和右端点加入离散化数组pri。
}
sort(pri.begin(),pri.end());
pri.erase(unique(pri.begin(),pri.end()),pri.end());
s=pri.size();
build(1,s,1);//0下标的位置没有前一个，所以从1开始建树。
for(int i=1;i<=q;++i)
{
//lower_bound返回大于等于给定值的下标，插入操作时是插入的opl[i]-1和opr[i]，所以查询大于等于opl[i]的下标可以查询到opl[i]所在的块。
if(op[i]==1) update(1,s,1,lower_bound(pri.begin(),pri.end(),opl[i])-pri.begin(),lower_bound(pri.begin(),pri.end(),opr[i])-pri.begin(),opx[i]);
else printf("%d\n",find(1,s,1,lower_bound(pri.begin(),pri.end(),opl[i])-pri.begin(),lower_bound(pri.begin(),pri.end(),opr[i])-pri.begin()));
}
return 0;
}58.P5305 [GXOI/GZOI2019]旧词
> 浮生有梦三千场
> 穷尽千里诗酒荒
> 徒把理想倾倒
> 不如早还乡
>
> 温一壶风尘的酒
> 独饮往事迢迢
> 举杯轻思量
> 泪如潮青丝留他方
>
> ——乌糟兽/愚青《旧词》
你已经解决了五个问题，不妨在这大树之下，吟唱旧词一首抒怀。最后的问题就是关于这棵树的，它的描述很简单。
给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。
给定常数 $k$。
给定 $Q$ 个询问，每次询问给定 $x,y$。
求：
$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$
$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。
由于答案可能很大，你只需要输出答案模 $998244353$ 的结果。
这道题目非常简洁：要求 $\sum_{i\le x}depth(lca(i,y))^k$ （都写在题面里了）
要直接解决这个问题是有点困难的，那么——
我们先看它的弱化版：[[LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211)
要求 $\sum_{i=l}^rdepth(lca(i,z))$
少了个k次方呢！
首先转化一下 $\sum_{i=l}^rdepth(lca(i,z))=\sum_{i=1}^rdepth(lca(i,z))-\sum_{i=1}^{l-1}depth(lca(i,z))$
可以用前缀和来解决这个问题。
把每个询问拆成 $(1,l-1)$ 和 $(1,r)$ 分别解决。
那么我们可以按顺序把 $1$ 到 $n$ 的点加进来，同时计算加到每个点时的询问答案。
那么现在考虑加到第 $i$ 个点时如何计算贡献。
先上张图举个例子~
其中涂成红色的点就是已经加入的点。
我们先计算一下每个节点的子树中有多少已经加入的点，用 $siz[x]$ 表示。没有加入的节点对当前询问肯定没有贡献。所以我们直接统计加入的节点就好了
那么 $siz[1]=4$ , $siz[2]=2$, $siz[3]=1$, $siz[4]=1$ , $siz[5]=1$ , $siz[6]=0$ .
现在考虑计算当前加入的节点到4的LCA深度和。
$ans=siz[4]\times dep[4]+(siz[2]-siz[4])\times dep[2]+(siz[1]-siz[2])\times dep[1]$
即加入的节点中在 $4$ 的子树中的到 $4$ 的 $LCA$ 肯定为 $4$。在 $2$ 的子树但不在 $4$ 的子树中的到 $4$ 的 $LCA$ 肯定为 $2$，在 $1$ 的子树但不在 $2$ 的子树中的到 $4$ 的 $LCA$ 肯定为 $1$。
把式子拆开化简得到:
$ans=siz[4]\times (dep[4]-dep[2])+siz[2]\times (dep[2]-dep[1])+siz[1]$
$ans=siz[4]+siz[2]+siz[1]$
于是我们发现其实答案就是该节点到根路径的节点子树大小之和。
普遍形式：设查询节点到根的路径为 $\{v_1,v_2,v_3\dots v_k\}$。
$ans=siz[v_1]\times dep[v_1]+(siz[v_2]-siz[v_1])\times dep[v_2]+(siz[v_3]-siz[v_2])\times dep[v_3]+\dots +(siz[v_k]-siz[v_{k-1}])\times dep[v_k]$
由于是到根节点的路径，所以 $dep[v_i]=dep[v_{i+1}]+1$
于是化简得
$ans=siz[v_1]\times (dep[v_1]-dep[v_2])+siz[v_2]\times (dep[v_2]-dep[v_3])+siz[v_3]\times (dep[v_3]-dep[v_4])+\dots +siz[v_k]\times dep[v_k]$
$ans=siz[v_1]+siz[v_2]+siz[v_3]+\dots +siz[v_k]$
就此得出结论：答案就是该节点到根路径的节点子树大小之和。
查询直接查询要查询的节点到根路径上的节点的子树大小之和。
加入节点时只有它到根的路径上的节点的子树大小加了一。
使用树链剖分加线段树维护即可。
回到本题
本题没有 $l$ 的限制，所以我们不用前缀和拆询问处理了。
那么我们抬出之前的式子改成这道题的样子。
$ans=siz[v1]\times dep[v1]^k+(siz[v2]-siz[v1])\times dep[v2]^k+(siz[v3]-siz[v2])\times dep[v3]^k+\dots+(siz[vk]-siz[vk-1])\times dep[vk]^k$
化简一下，得到：
$ans=siz[v_1]\times (dep[v_1]^k-dep[v_2]^k)+siz[v_2]\times (dep[v_2]^k-dep[v_3]^k)+siz[v_3]\times (dep[v_3]^k-dep[v4]^k)+\dots siz[v_k]\times dep[v_k]^k$
可以发现，$dep[v_2]$ 总等于 $dep[v_1]-1$（因为是从查询节点到根节点的路径嘛）。
所以对于$(dep[v_i]^k-dep[v_{i+1}]^k)$这种东西，我们可以对它进行预处理。
设对于点i的预处理答案为 $val[i]$。
则答案为:
$ans=siz[v_1]\times val[v_1]+siz[v_2]\times val[v_2]+siz[v_3]\times val[v_3]+...siz[v_k]\times val[v_k]$
就是在线段树维护时多加一个权值的问题了。
在线段树的每个节点上附加一个权值，表示这个区间里所有点的 $val$ 之和。
这样就可以区间修改和下传标记了。
跟上面那道弱化版差得不多吧~
代码：
//直接用LCA代码改的，可能有点迷惑（？
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long> e[50010];
struct node
{
long long bas,sum,tag;//bas为附加的权值
}nodes[400010];
struct ask
{
long long pos,val,ID,nag;
}q[100010];
bool cmp(ask one,ask ano)
{
return one.pos<ano.pos;
}
long long n,m,s,opl,opr,opz,f,cnt,tot,waste,ans[50010],kkk,dep[50010],fa[50010],son[50010],siz[50010],hb[50010],dfn[50010],ton[50010],power[50010],bruh;
const long long mod=998244353;
long long qpow(long long bas,long long tim)//快速幂用来处理val
{
long long res=1,fur=bas;
while(tim)
{
if(tim&1) res=(res*fur)%mod;
fur=(fur*fur)%mod;
tim>>=1;
}
return res;
}
void dfs(long long x,long long las)
{
fa[x]=las;
dep[x]=dep[las]+1;
siz[x]=1;
long long b=0,s=0;
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i];
dfs(y,x);
siz[x]+=siz[y];
if(siz[y]>b)
{
b=siz[y];
s=y;
}
}
son[x]=s;
}
void dfs2(long long x,long long las,long long heavy)//树剖dfs
{
if(heavy) hb[x]=hb[las];
else hb[x]=x;
dfn[x]=++cnt;
ton[cnt]=x;
if(son[x]) dfs2(son[x],x,1);
for(long long i=0;i<e[x].size();++i)
{
long long y=e[x][i];
if(y^son[x]) dfs2(y,x,0);
}
}
void pushdown(long long x)
{
if(nodes[x].tag)
{
//(siz[x]+a)*val[x]+(siz[y]+a)*val[y]+...+(siz[z]+a)*val[z]
//=siz[x]*val[x]+siz[y]*val[y]+...+siz[z]*val[z]+a*(val[x]+val[y]+...+val[z])
nodes[x].sum+=(nodes[x].bas*nodes[x].tag);
nodes[x].sum%=mod;
nodes[x<<1].tag+=nodes[x].tag;
nodes[x<<1].tag%=mod;
nodes[x<<1|1].tag+=nodes[x].tag;
nodes[x<<1|1].tag%=mod;
nodes[x].tag=0;
}
}
void build(long long l,long long r,long long x)//预处理val区间和
{
if(l^r)
{
long long mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
nodes[x].bas=(nodes[x<<1].bas+nodes[x<<1|1].bas)%mod;
}
else nodes[x].bas=power[dep[ton[l]]]-power[dep[ton[l]]-1];
// printf(" %lld %lld %lld\n",l,r,nodes[x].bas);
}
void update(long long l,long long r,long long x,long long fr,long long ba)
{
if(l>ba||r<fr) return;
if(l>=fr&&r<=ba) nodes[x].tag=(nodes[x].tag+1)%mod;
else
{
pushdown(x);
long long mid=(l+r)>>1;
update(l,mid,x<<1,fr,ba);
update(mid+1,r,x<<1|1,fr,ba);
pushdown(x<<1);
pushdown(x<<1|1);
nodes[x].sum=(nodes[x<<1].sum+nodes[x<<1|1].sum)%mod;
}
}
long long find(long long l,long long r,long long x,long long fr,long long ba)
{
if(l>ba||r<fr) return 0;
pushdown(x);
if(l>=fr&&r<=ba) return nodes[x].sum;
else
{
long long mid=(l+r)>>1;
return (find(l,mid,x<<1,fr,ba)+find(mid+1,r,x<<1|1,fr,ba))%mod;
}
}
void output(long long l,long long r,long long x)
{
pushdown(x);
printf(" %lld %lld %lld\n",l,r,nodes[x].sum);
if(l^r)
{
long long mid=(l+r)>>1;
output(l,mid,x<<1);
output(mid+1,r,x<<1|1);
}
}
void update_LCA(long long x,long long y)
{
long long fx=hb[x],fy=hb[y];
while(fx^fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
update(1,s,1,dfn[fx],dfn[x]);
x=fa[fx];
fx=hb[x];
}
update(1,s,1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
}
long long find_LCA(long long x,long long y)
{
long long res=0;
long long fx=hb[x],fy=hb[y];
while(fx^fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
res+=find(1,s,1,dfn[fx],dfn[x]);
res%=mod;
x=fa[fx];
fx=hb[x];
}
res+=find(1,s,1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
res%=mod;
return res;
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&bruh);
s=n;
for(long long i=1;i<=n;++i) power[i]=qpow(i,bruh);
for(long long i=2;i<=n;++i)
{
scanf("%lld",&f);
e[f].push_back(i);
}
dfs(1,1);
dfs2(1,1,0);
build(1,s,1);
for(long long i=1;i<=m;++i)
{
scanf("%lld %lld",&opr,&opz);
q[++tot].ID=i;
q[tot].nag=1;
q[tot].pos=opr;
q[tot].val=opz;
}
sort(q+1,q+1+tot,cmp);
while(q[kkk].pos<=0&&kkk<=tot)
{
ans[q[kkk].ID]+=(q[kkk].nag*0);
++kkk;
}
for(long long i=1;i<=n;++i)
{
update_LCA(1,i);
while(q[kkk].pos<=i&&kkk<=tot)
{
ans[q[kkk].ID]+=(q[kkk].nag*find_LCA(1,q[kkk].val));
ans[q[kkk].ID]%=mod;
++kkk;
}
// puts("");
// output(1,s,1);
// puts("\n");
}
for(long long i=1;i<=m;++i) printf("%lld\n",((ans[i]%mod)+mod)%mod);
return 0;
}59.CF643G Choosing Ads
- 给定一个长度为 $n$ 的序列和一个整数 $p$。
- 有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。
- 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}{p} \rfloor$。
题意简述
够简单了。
题解
我觉得很有意思的一道题目。
第一个操作，嗯，不讲。
我们着重来看看第二个操作。
这个查询操作要我们输出所有出现次数的频率 $\ge p\%$ 的数字。
先考虑一种特殊情况，即当 $p>50$ 的情况，这时候这个问题的本质就成了求区间的绝对众数。
区间绝对众数有一个经典的 $\Theta(1)$ 空间的做法，摩尔投票。
这里简单介绍一下摩尔投票法。
举个例子，序列 $\texttt{7 5 7 6 7 7 4 7}$。
我们定义两个变量 major,cnt。
我们遍历一遍序列：
起初 major=7,cnt=1。
然后 $5\neq 7$，cnt--。
此时 cnt==0，我们令 major=5,cnt=1。
后面以此类推。
那么拓展到这道题目，我们的 p 最小是 20。
和普通的摩尔投票法类似，我们把 major,cnt 替换为 major[5],cnt[5]，用数组来求出分别的众数。
不过这样做有可能会出现出现频率不符合答案规范的数存进来，不过反正良心出题人允许我们输出无意义内容，所以就不用管了。
然后考虑用一个数据结构来加速这个过程。
区间推平、查询首选线段树。
那么要维护的信息就很明显了。
每个结点维护一个摩尔投票的结构体，然后再维护一个区间推平的 tag。
最后 pushup 合并左右儿子贡献时，直接把右区间合并到左边来即可。
下传标记很简单，不过要注意下传时因为时区间推平，所以摩尔投票的结构体里的 cnt 部分要设为 r-l+1。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <assert.h>
using namespace std;
const int Maxn = 15e4 + 5;
int n, m, p, isa[Maxn];
struct Major_Voting // 摩尔投票的结构体
{
int major[5], cnt[5];
Major_Voting()
{
memset(major, 0, sizeof(major));
memset(cnt, 0, sizeof(cnt));
}
};
struct Segment_Tree
{
Major_Voting val;
int tag;
} t[Maxn << 2];
Major_Voting make_vote(int major) // 以 major 为关键字创建一个新的摩尔投票
{
Major_Voting ret;
memset(ret.major, 0, sizeof(ret.major));
memset(ret.cnt, 0, sizeof(ret.cnt));
ret.major[0] = major;
ret.cnt[0] = 1;
return ret;
}
Major_Voting merge(Major_Voting one, Major_Voting ano) // 合并区间，这一步的细节较多
{
Major_Voting ret = one;
for (int i = 0; i < p; ++i)
{
if (ano.cnt[i])
{
bool flag = 0;
for (int j = 0; j < p; ++j)
{
if (ret.major[j] == ano.major[i])
{
ret.cnt[j] += ano.cnt[i];
flag = 1;
break;
}
}
if (flag == 0)
{
for (int j = 0; j < p; ++j)
{
if (ret.cnt[j] == 0)
{
ret.major[j] = ano.major[i];
ret.cnt[j] = ano.cnt[i];
flag = 1;
break;
}
}
} // 把右区间的贡献算到左边来
if (flag) continue;
int line = 2e9;
for (int j = 0; j < p; ++j) line = min(line, ret.cnt[j]);
if (line >= ano.cnt[i])
{
for (int j = 0; j < p; ++j) ret.cnt[j] -= ano.cnt[i];
continue;
}
bool book = 0;
for (int j = 0; j < p; ++j)
{
if (ret.cnt[j] == line && book == 0)
{
ret.major[j] = ano.major[i];
ret.cnt[j] = ano.cnt[i] - line;
book = 1;
}
else ret.cnt[j] -= line;
} // 分类讨论最小值的处理
}
}
return ret;
}
void maintain(int p)
{
t[p].val = merge(t[p << 1].val, t[p << 1 | 1].val);
}
void spread(int p, int l, int r)
{
if (t[p].tag)
{
int mid = (l + r) >> 1;
t[p << 1].tag = t[p].tag;
t[p << 1 | 1].tag = t[p].tag;
t[p << 1].val = make_vote(t[p].tag);
t[p << 1].val.cnt[0] = mid - l + 1;
t[p << 1 | 1].val = make_vote(t[p].tag);
t[p << 1 | 1].val.cnt[0] = r - mid;
t[p].tag = 0;
}
}
void build(int p, int l, int r)
{
if (l == r)
{
t[p].val = make_vote(isa[l]);
return ;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
maintain(p);
}
void change(int p, int l, int r, int x, int y, int v)
{
if (l > y || r < x) return ;
if (l >= x && r <= y)
{
t[p].tag = v;
t[p].val = make_vote(v);
t[p].val.cnt[0] = r - l + 1;
return ;
}
int mid = (l + r) >> 1;
spread(p, l, r);
if (mid >= x) change(p << 1, l, mid, x, y, v);
if (mid < y) change(p << 1 | 1, mid + 1, r, x, y, v);
maintain(p);
}
Major_Voting query(int p, int l, int r, int x, int y)
{
if (l > y || r < x) return make_vote(0);
if (l >= x && r <= y) return t[p].val;
int mid = (l + r) >> 1;
Major_Voting ret;
spread(p, l, r);
if (mid >= x) ret = merge(ret, query(p << 1, l, mid, x, y));
if (mid < y) ret = merge(ret, query(p << 1 | 1, mid + 1, r, x, y));
return ret;
} // 以上板子
signed main()
{
scanf("%d %d %d", &n, &m, &p);
assert(p >= 20 && p <= 100);
p = 100 / p;
for (int i = 1; i <= n; ++i) scanf("%d", &isa[i]);
build(1, 1, n);
for (int i = 0, t, l, r, x; i < m; ++i)
{
scanf("%d %d %d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &x);
change(1, 1, n, l, r, x);
}
else
{
Major_Voting ans = query(1, 1, n, l, r);
printf("%d", p);
for (int i = 0; i < p; ++i) printf(" %d", ans.major[i]); // 因为题目的特殊性，我们可以随便乱输出
putchar('\n');
}
}
return 0;
}60.P5071 [Ynoi2015]此时此刻的光辉
珂朵莉给你了一个长为 $n$ 的序列，有 $m$ 次查询，每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。
我们知道一个结论：
若 $n=\Pi_{i=1}^kp_i^{a_i}$。
则 $n$ 的约数个数为 $\Pi_{i=1}^k(a_i+1)$。
知道这个结论之后，我们就有一个 自 然 而 然 的想法：
用莫队维护每个质因数的出现次数和答案。
每加入或删除一个质因数，就先乘上它之前出现的次数加一的逆元，然后把出现次数加上或减去一之后再乘。
一算时间复杂度，每个数最多会有 $9$ 个质因数，那么序列中会有 $9\times 10^5$ 个数。莫队跑不过去。
但我们发现：小的质因数很多。我们可以抓住这一点进行优化。
由于只用知道每个质因数出现的次数就可以了。
我们可以把这些小的质因数都筛出来，做个前缀和，每次询问都单独统计乘上去。
这里我是把 $\sqrt{10^9}$ 以内的质数都筛出来了（用来筛其他的大的质因数），然后把前 $200$ 个的出现次数拿来做前缀和。
之前人傻了写线段树卡了半天常
代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
vector<int> p;
int prime[100010],cntot,tag[100010];
void search(int x)//线性筛质数
{
tag[1]=1;
for(int i=2;i<=x;++i)
{
if(!tag[i]) prime[++cntot]=i;
for(int j=1;j<=cntot&&prime[j]*i<=x;++j)
{
tag[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
struct ask
{
int l,r,ID,lyc,wgy;//lyc和wgy表示这个询问在原序列上的左右端点，用来之后查询小的质因数的出现个数
}as[100010];
const int each=700,mod=19260817;
int n,m,a[100010],cnt[100010][201],nodes[100010][201],ton[201],pri[200010],belong[200010],ans[100010],in[100010],out[100010],inv[200010],tot,opl,opr,nowl,nowr,app[200010],cur=1;
bool cmp(ask one,ask ano)
{
if(belong[one.l]^belong[ano.l]) return belong[one.l]<belong[ano.l];
if(belong[one.l]&1) return one.r<ano.r;//奇偶排序
else return one.r>ano.r;
}
void read(int &hhh)
{
int x=0;
char c=getchar();
while((c<'0')|(c>'9')&&c^'-') c=getchar();
if(c^'-') x=c^'0';
char d=getchar();
while((d<='9')&(d>='0'))
{
x=(x<<1)+(x<<3)+(d^'0');
d=getchar();
}
if(c^'-') hhh=x;
else hhh=-x;
}
void writing(int x)
{
if(!x) return;
writing(x/10);
putchar((x%10)+'0');
}
void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
else if(!x)
{
putchar('0');
putchar('\n');
return;
}
writing(x);
putchar('\n');
}
int main()
{
read(n);
read(m);
search(33000);
for(int i=1;i^201;++i) ton[i]=prime[i];
for(int i=1;i<=n;++i)
{
read(a[i]);
in[i]=tot+1;//in[],out[]记录每个原序列的元素质因数在新的序列中的开头结尾
for(int j=1;j^201;++j)
{
while(a[i]%ton[j]==0)
{
a[i]/=ton[j];
++cnt[i][j];
}
}
if(a[i]>1)
{
for(int j=201;prime[j]*prime[j]<=a[i];++j)//把大的质因数拿出来作为一个新的序列
{
while(a[i]%prime[j]==0)
{
a[i]/=prime[j];
pri[++tot]=prime[j];
}
}
if(a[i]>1) pri[++tot]=a[i];
}
out[i]=tot;
}
inv[1]=1;
for(int i=2;i<=tot;++i) inv[i]=(((-(long long)(mod/i)*inv[mod%i])%mod)+mod)%mod;//线性处理逆元
for(int i=1;i<=tot;++i)
{
p.push_back(pri[i]);
belong[i]=(i-1)/each+1;
}
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
for(int i=1;i<=tot;++i) pri[i]=lower_bound(p.begin(),p.end(),pri[i])-p.begin()+1;
for(int i=1;i^201;++i)//对小的质因数做前缀和
{
for(int j=1;j<=n;++j) nodes[j][i]=nodes[j-1][i]+cnt[j][i];
}
for(int i=1;i<=m;++i)
{
read(opl);
read(opr);
as[i].l=in[opl];
as[i].r=out[opr];//莫队的询问左右端点，把原序列中查询区间的质因数全部覆盖掉。
as[i].ID=i;
as[i].lyc=opl;
as[i].wgy=opr;
}
sort(as+1,as+1+m,cmp);
nowl=1;
for(int i=1;i<=m;++i)
{
while(nowl>as[i].l)
{
--nowl;
cur=((long long)cur*inv[app[pri[nowl]]+1])%mod;//先乘上以前的逆元，消除之前的答案贡献
++app[pri[nowl]];
cur=((long long)cur*(app[pri[nowl]]+1))%mod;//乘上现在的答案贡献
}
while(nowr<as[i].r)
{
++nowr;
cur=((long long)cur*inv[app[pri[nowr]]+1])%mod;
++app[pri[nowr]];
cur=((long long)cur*(app[pri[nowr]]+1))%mod;
}
while(nowl<as[i].l)
{
cur=((long long)cur*inv[app[pri[nowl]]+1])%mod;
--app[pri[nowl]];
cur=((long long)cur*(app[pri[nowl]]+1))%mod;
++nowl;
}
while(nowr>as[i].r)
{
cur=((long long)cur*inv[app[pri[nowr]]+1])%mod;
--app[pri[nowr]];
cur=((long long)cur*(app[pri[nowr]]+1))%mod;
--nowr;
}
int tmp=cur;
for(int j=1;j^201;++j) tmp=((long long)tmp*(nodes[as[i].wgy][j]-nodes[as[i].lyc-1][j]+1))%mod;//临时乘上小的质因数对答案的贡献
ans[as[i].ID]=tmp;
}
for(int i=1;i<=m;++i) write(ans[i]);
return 0;
}Ds100p -「数据结构百题」41~50
41.P3590 [POI2015]TRZ
给定一个长度为n的仅包含'B'、'C'、'S'三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。
题意简述
题意够简单了就不说了。
题解
暴力能过。
开三个数组前缀和一下每个字母出现的次数，然后枚举长度暴力check就过了。
暴力就这么点东西。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
int n, b[N], c[N], s[N];
char str[N];
bool check(int p) {
for (int i = 1; i <= n - p + 1; ++i) {
int s1 = b[i + p - 1] - b[i - 1];
int s2 = c[i + p - 1] - c[i - 1];
int s3 = s[i + p - 1] - s[i - 1];
if (s1 != s2 && s2 != s3 && s1 != s3) return true;
}
return false;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> str;
for (int i = 0; i < n; ++i) {
char ch = str[i];
if (ch == 'B') b[i + 1] = 1;
else if (ch == 'C') c[i + 1] = 1;
else s[i + 1] = 1;
}
for (int i = 1; i <= n; ++i) {
b[i] += b[i - 1];
c[i] += c[i - 1];
s[i] += s[i - 1];
}
for (int i = n; i >= 1; --i)
if (check(i)) return printf("%d\n", i), 0;
return puts("1"), 0;
}42.P4688 [Ynoi2016]掉进兔子洞
您正在打 galgame，然后突然发现您今天太颓了，于是想写个数据结构题练练手：
一个长为 $n$ 的序列 $a$。
有 $m$ 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。
注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，比如三个区间是 $[1,2,2,3,3,3,3]$，$[1,2,2,3,3,3,3]$ 与 $[1,1,2,3,3]$，就一起扔掉了 $1$ 个 $1$，$1$ 个 $2$，$2$ 个 $3$。
题意简述
Ynoi的题貌似题面都很简洁……（除了惯例的一大堆Gal或Anime的图片+对话以外）
题解
读完题，我们可以发现每轮询问的答案是这个东西:
$$ \sum_{i=1}^{3}(r_{i}-l_{i}+1)-P\times 3 $$
其中，$P$ 表示三个区间里面的公共颜色数量。
前面那个 $\sum$ 里面的东西很好维护，我们主要来讲后面一部分的维护方法。
首先初始序列的 $a_{i}$ 是一定要离散化一遍的。
那么我们如何表示出出现的最少次数呢？
如果这是一个二进制串的话，我们可以发现这就是一个 $\operatorname{bit\_and}$ 的操作。
对于每个询问，我们可以把三个区间分开处理再合并。直接维护复杂度过高，用 bitset 优化。由于这是个二进制序列，所以离散化的时候不能去重，否则答案就会偏大。
直接操作容易 MLE，这里介绍一个小trick。我们可以把询问分批处理，这样就行了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <bitset>
#include <cmath>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 5;
const int F = 23333 + 5;
int n, m, block, origin[N], appear[N];
int cnt[N], ans[N], vis[25005];
int l1[N], l2[N], l3[N];
int r1[N], r2[N], r3[N];
bitset < N > S[F];
vector < int > disc;
struct AskSet {
int l, r;
int id, p;
} Q[N];
int GetID(int x) {
return lower_bound(disc.begin(), disc.end(), x) - disc.begin() + 1;
}
bool SortWith(const AskSet& x, const AskSet& y) {
return (x.p < y.p) || (x.p == y.p && x.r < y.r);
}
void MakeCont(int pos, int flags, bitset < N >& bit) {
pos = origin[pos];
if (flags > 0) bit[pos + cnt[pos]] = 1;
else bit[pos + cnt[pos] - 1] = 0;
cnt[pos] += flags;
}
void Contribute(int fr, int ba) {
memset(cnt, 0, sizeof cnt);
memset(vis, 0, sizeof vis);
bitset < N > bit; bit.reset();
int l = 1, r = 0, subs = 0;
for (int i = fr; i <= ba; ++i) {
Q[++subs] = {l1[i], r1[i], i, appear[l1[i]]};
Q[++subs] = {l2[i], r2[i], i, appear[l2[i]]};
Q[++subs] = {l3[i], r3[i], i, appear[l3[i]]};
ans[i] += (r3[i] - l3[i]) + (r2[i] - l2[i]) + (r1[i] - l1[i]) + 3;
}
sort(Q + 1, Q + 1 + subs, SortWith);
for (int i = 1; i <= subs; ++i) {
while (r < Q[i].r) MakeCont(++r, 1, bit);
while (l > Q[i].l) MakeCont(--l, 1, bit);
while (r > Q[i].r) MakeCont(r--, -1, bit);
while (l < Q[i].l) MakeCont(l++, -1, bit);
if (!vis[Q[i].id - fr + 1]) {
vis[Q[i].id - fr + 1] = 1;
S[Q[i].id - fr + 1] = bit;
} else {
S[Q[i].id - fr + 1] &= bit;
}
}
for (int i = fr; i <= ba; ++i)
ans[i] -= S[i - fr + 1].count() * 3;
}
signed main() {
scanf("%d %d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &origin[i]);
appear[i] = (i - 1) / block + 1;
disc.push_back(origin[i]);
}
sort(disc.begin(), disc.end());
for (int i = 1; i <= n; ++i)
origin[i] = GetID(origin[i]);
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &l1[i], &r1[i]);
scanf("%d %d", &l2[i], &r2[i]);
scanf("%d %d", &l3[i], &r3[i]);
}
for (int i = 1; i <= m; i += 23333) Contribute(i, min(m, i + 23332));
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}43.P3224 [HNOI2012]永无乡
永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座（含 $0$ 座）桥可以 到达岛 $b$ ，则称岛 $a$ 和岛 $b$ 是连通的。
现在有两种操作：
B x y 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。
Q x k 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。
题意简述
现在有n个点和两种操作：
B x y 表示连接 x 与 y。
Q x k 表示询问 x 所在连通块里的第 k 小权值。
题解
首先一看到第k小，我们就想到用权值线段树或者平衡树来维护一个连通块里的值。
但是这道题要求连接两个连通块,单纯的权值线段树肯定不行。而一个节点一个节点暴力合并肯定会超时。
所以我们就打线段树合并罢！
线段树合并其实也挺暴力的。
它和真正的暴力合并只是如果要合并的两颗线段树中有一个没有当前要合并的节点，那么就直接把另一个线段树的节点接在这里。
其实就是一个剪枝对吧
这道题的权值个数只有n个，而且每个权值只有一个。
所以这个剪枝的作用很大。
那这道题的算法就是这样的：
用并查集维护连通块，用权值线段树维护值。
每次要合并两个连通块时，把 x 所在连通块和 y 所在连通块接在一起，然后合并这两个连通块的线段树。
查询就正常查询就好了。
代码：
#include<cstdio>
int n,m,fa[300010],u,v,cnt,mpp[300010],opx,opy,root[300010],q;
char op;
struct node
{
int l,r,num;
}nodes[30000010];
int finds(int x)//寻找 x 所在连通块编号。
{
if(fa[x]^x) fa[x]=finds(fa[x]);
return fa[x];
}
void ins(int l,int r,int &x,int pos)//初始时每个点都是一个连通块，提前处理它的线段树。
{
nodes[x=++cnt].num=1;
if(l^r)
{
int mid=(l+r)>>1;
if(pos<=mid) ins(l,mid,nodes[x].l,pos);
else ins(mid+1,r,nodes[x].r,pos);
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;//有一个没有或两个都没有， x+y 返回不是 0 的那个或者因为两个都没有而返回0。
else
{
nodes[x].num+=nodes[y].num;//合并本节点。
nodes[x].l=merge(nodes[x].l,nodes[y].l);//
nodes[x].r=merge(nodes[x].r,nodes[y].r);//合并左右儿子。
return x;//前面的信息储存到的是 x 这个节点那就返回 x 。
}
}
int find(int l,int r,int x,int k)//权值线段树正常查询。
{
if(l^r)
{
int mid=(l+r)>>1;
if(nodes[nodes[x].l].num>=k) return find(l,mid,nodes[x].l,k);
else return find(mid+1,r,nodes[x].r,k-nodes[nodes[x].l].num);
}
else return l;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=n;++i)
{
scanf(" %d",&u);
mpp[u]=i;//记录每个权值对应的节点编号，便于之后输出。
ins(1,n,root[i],u);
}
for(int i=1;i<=m;++i)
{
scanf(" %d %d",&u,&v);
int U=finds(u);//这些初始边也相当于从没有边开始进行加边操作。
int V=finds(v);
if(U^V)
{
fa[U]=V;
root[V]=merge(root[U],root[V]);//把 U 接到 V 上面了就要把 U 的线段树合并到 V 的线段树上。
}
}
scanf(" %d",&q);
for(int i=1;i<=q;++i)
{
scanf(" %c %d %d",&op,&opx,&opy);
if(op=='Q')
{
int OPX=finds(opx);
if(nodes[root[OPX]].num>=opy) printf("%d\n",mpp[find(1,n,root[OPX],opy)]);//查询第 k 小的值，输出对应的节点编号。
else printf("-1\n");//这个连通块没有那么多点，输出 -1 。
}
else
{
int OPX=finds(opx);
int OPY=finds(opy);
if(OPX^OPY)
{
fa[OPX]=OPY;
root[OPY]=merge(root[OPX],root[OPY]);
}
}
}
return 0;
}44.P5795 [THUSC2015]异或运算
给定长度为 $n$ 的数列 $X={x_1,x_2,...,x_n}$ 和长度为 $m$ 的数列 $Y={y_1,y_2,...,y_m}$，令矩阵 $A$ 中第 $i$ 行第 $j$ 列的值 $A_{i,j}=x_i\ \operatorname{xor}\ y_j$，每次询问给定矩形区域 $i∈[u,d],j∈[l,r]$，找出第 $k$ 大的 $A_{i,j}$。
题意简述
根据两个数列做一个矩阵，给定几组询问，求一个矩形区域里的k大值
题解
可以发现 $N$ 很小，所以我们可以暴力枚举每个 $X_{i}$，然后对每个 $Y_{i}$ 建一个可持久化Trie树，插入即可。
对于询问，直接按照持久化Trie的查询套路来即可。首先记录root，然后我们就可以在查询时根据 $K$ 的大小来递归。
具体来说，就是往当前节点的哪个儿子走能使xor的结果的为1，然后根据从cnt的值判断递归方向。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
const int N = 300000 + 5;
int n, m, q, tot, wrt[N][2], trie[N * 40][2], frie[N * 40], root[N], X[N], Y[N];
int ins(int prt, int val) {
int now = ++tot, res = now;
for (int i = 31; ~i; --i) {
int bit = (val >> i) & 1;
trie[now][bit ^ 1] = trie[prt][bit ^ 1];
prt = trie[prt][bit];
now = trie[now][bit] = ++tot;
frie[now] = frie[prt] + 1;
}
return res;
}
int ret(int x1, int x2, int y1, int y2, int k) {
k = (x2 - x1 + 1) * (y2 - y1 + 1) - k + 1;
for (int i = x1; i <= x2; ++i) {
wrt[i][0] = root[y1 - 1];
wrt[i][1] = root[y2];
}
int res = 0, cnt = 0;
for (int i = 31; ~i; --i) {
for (int j = x1; j <= x2; ++j) {
int bit = (X[j] >> i) & 1;
int now0 = wrt[j][0], now1 = wrt[j][1];
cnt += frie[trie[now1][bit]] - frie[trie[now0][bit]];
}
int flags;
if (k > cnt) k -= cnt, flags = 1;
else flags = 0;
res <<= 1, res |= flags;
for (int j = x1; j <= x2; ++j) {
int bit = ((X[j] >> i) & 1) ^ flags;
int &now0 = wrt[j][0], &now1 = wrt[j][1];
now0 = trie[now0][bit];
now1 = trie[now1][bit];
}
cnt = 0;
}
return res;
}
signed main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &X[i]);
for (int i = 1; i <= m; ++i) {
scanf("%d", &Y[i]);
root[i] = ins(root[i - 1], Y[i]);
}
scanf("%d", &q);
for (int i = 0, x1, x2, y1, y2, k; i < q; ++i) {
scanf("%d %d %d %d %d", &x1, &x2, &y1, &y2, &k);
printf("%d\n", ret(x1, x2, y1, y2, k));
}
return 0;
}45.P3674 小清新人渣的本愿
这个题是这样的：
给你一个序列 $a$，长度为 $n$，有 $m$ 次操作，每次询问一个区间是否可以选出两个数它们的差为 $x$，或者询问一个区间是否可以选出两个数它们的和为 $x$，或者询问一个区间是否可以选出两个数它们的乘积为 $x$ ，这三个操作分别为操作 $1,2,3$。
选出的这两个数可以是同一个位置的数。
题意简述
尽管题意已经够简洁了但是我还是要坚持我的题解风格
题解
dllxl难的的一个比较水的题。
我们初一看这道题目。没修改，不强制在线，基本上大思路就往莫队走了。
考虑一种暴力做法，对三个操作分别开桶算贡献，加法减法的计算方法比较简单，加法就是减法的逆运算，反着开就行了。乘法直接枚举约数，毕竟这道题的值域和数列长度及询问是一样的。
发现容易炸，又因为我们的桶是根据存在性开的，所以我们可以用bitset来优化。
记录两个bitset为classic和inverse。
如果为操作一的话就是：
$$ \operatorname{ANS_{Q_{i}->id}}=(\operatorname{classic\ bitand\ (classic\ shl\ Q_{i}->x)}).\operatorname{any()} $$
操作二类似：
$$ \operatorname{ANS_{Q_{i}->id}}=(\operatorname{classic\ bitand\ (inverse\ shr\ (100000-Q_{i}->x))}).\operatorname{any()} $$
操作三则直接枚举。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is() (ch >= '0' && ch <= '9')
template < typename Type >
void read(Type& a) {
a = 0; char ch; bool f = 0;
while (!(ch = gc(), is())) if (ch == '-') f = 1;
while (is()) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
a = (f ? -a : a);
}
template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
read(t), read(args...);
}
const int N = 1e5 + 5, R = 100000;
struct Query_Node {
int id, pos;
int tp, l, r, x;
bool operator < (const Query_Node& rhs) const {
if (pos != rhs.pos) return pos < rhs.pos;
else return r < rhs.r;
}
} e[N];
int n, m, Size, a[N], cnt[N], ans[N];
bitset < N > classic, inverse;
void Add(int x) {
++cnt[a[x]];
if (cnt[a[x]] == 1) {
classic[a[x]] = 1;
inverse[R - a[x]] = 1;
}
}
void Del(int x) {
--cnt[a[x]];
if (cnt[a[x]] == 0) {
classic[a[x]] = 0;
inverse[R - a[x]] = 0;
}
}
void Contribute() {
int l = 1, r = 0;
for (int i = 1; i <= m; ++i) {
while (l < e[i].l) Del(l++);
while (l > e[i].l) Add(--l);
while (r > e[i].r) Del(r--);
while (r < e[i].r) Add(++r);
if (e[i].tp == 1) {
ans[e[i].id] = (classic & (classic << e[i].x)).any();
} else if (e[i].tp == 2) {
ans[e[i].id] = (classic & (inverse >> (R - e[i].x))).any();
} else {
for (int j = 1; j * j <= e[i].x; ++j) {
if (e[i].x % j == 0 && classic[j] && classic[e[i].x / j])
ans[e[i].id] = 1;
}
}
}
}
signed main() {
read(n, m), Size = sqrt(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= m; ++i) {
read(e[i].tp, e[i].l, e[i].r, e[i].x);
e[i].id = i, e[i].pos = (e[i].l - 1) / Size + 1;
}
sort(e + 1, e + 1 + m);
Contribute();
for (int i = 1; i <= m; ++i) puts(ans[i] ? "hana" : "bi");
return 0;
}46.P3709 大爷的字符串题
给你一个字符串 $a$，每次询问一段区间的贡献。
贡献定义：
每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。
- 如果 $S$ 为空，你 rp 减 $1$。
- 如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
- 之后将 $x$ 插入 $S$。
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。
询问之间不互相影响~
题意简述
出题人语文……唉……
大意：给定几个询问，问一个区间最少被几个严格上升的序列覆盖。
可以转化为区间众数的出现次数。
题解
题面就不吐槽了。
不带修，可离线，考虑莫队。
我们可以维护两个东西。
一个是 $CNT_{x}$ 表示 $x$ 出现的次数。
还有一个就是 $APPEAR_{x}$ 表示出现次数为 $x$ 的数的数量。
$APPEAR_{x}$ 的定义有点绕，好好读一下。
莫队加贡献的时候就 appear[cnt[a[x]]]--,appear[++cnt[a[x]]]++ 即可。
意思就是出现次数为 cnt[a[x]] 的没了，减一个，后面的同理。
减贡献大体没什么区别，用一个全局变量 flags 记录答案的相反数。需要注意的是如果满足 cnt[a[x]]==flags && appear[cnt[a[x]]]==1 那么我们需要将 flags-1。后面的就和加贡献反着来即可。
局部代码：
const int N = 2e5 + 5;
int n, m, flags, Size, a[N], cnt[N], appear[N], ans[N];
vector < int > disc;
struct Query_Node {
int l, r, id, pos;
bool operator < (const Query_Node& rhs) const {
if (pos == rhs.pos)
return r < rhs.r;
else return pos < rhs.pos;
}
} e[N];
int Get_ID(int x) {
return lower_bound(disc.begin(), disc.end(), x) - disc.begin() + 1;
}
void Add(int x) {
appear[cnt[x]]--;
appear[++cnt[x]]++;
flags = max(flags, cnt[x]);
}
void Del(int x) {
if (cnt[x] == flags && appear[cnt[x]] == 1) --flags;
appear[cnt[x]]--;
appear[--cnt[x]]++;
}
void Contribute() {
int l = 1, r = 0;
for (int i = 1; i <= m; ++i) {
while (l < e[i].l) Del(a[l++]);
while (l > e[i].l) Add(a[--l]);
while (r > e[i].r) Del(a[r--]);
while (r < e[i].r) Add(a[++r]);
ans[e[i].id] = -flags;
}
}
signed main() {
read(n, m), Size = sqrt(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
disc.push_back(a[i]);
}
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (int i = 1; i <= n; ++i) a[i] = Get_ID(a[i]);
for (int i = 1; i <= m; ++i) {
read(e[i].l, e[i].r);
e[i].id = i;
e[i].pos = (e[i].l - 1) / Size;
}
sort(e + 1, e + 1 + m);
Contribute();
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}47.P3313 [SDOI2014]旅行
S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
“CC x c“：城市x的居民全体改信了c教；
“CW x w“：城市x的评级调整为w;
“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
题意简述
将树链剖分模板加了个限制。
题解
这道题如果考虑最暴力的做法就是树剖后对每一种宗教建立线段树统计。
实际上对每一种宗教建立线段树是没有必要的。
我们可以采取线段树动态开点的方法进行修改和查询，记录下每种宗教开点时的根节点。
对于操作一，我们可以直接将修改前的宗教改为0，这样就避免了删除操作。
其他的操作基本就是树剖的板子了，具体看代码吧。
还有一个坑点在于这道题如果用fread的话会WA完，和Dynamic Rankings一个尿性，具体原因我也不清楚。但是fread的话建议能不用就不用，容易出锅。
const int Maxn = 1e5 + 5;
int n, m, t_tot, root[Maxn], lev[Maxn], fai[Maxn];
int s_tot, siz[Maxn], dfn[Maxn], rnk[Maxn], top[Maxn], dep[Maxn], son[Maxn], fa[Maxn];
struct Tree_Node {
int ls, rs;
int _sum, _max;
} nodes[Maxn << 5];
vector < int > Graph[Maxn];
void dfs1(int x) {
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for (unsigned i = 0; i < Graph[x].size(); ++i) {
int y = Graph[x][i];
if (y == fa[x]) continue;
fa[y] = x;
dfs1(y);
if (siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x, int t) {
dfn[x] = ++s_tot;
rnk[dfn[x]] = x;
top[x] = t;
if (son[x]) dfs2(son[x], t);
for (unsigned i = 0; i < Graph[x].size(); ++i) {
int y = Graph[x][i];
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int newnode() {
int res = ++t_tot;
nodes[res].ls = nodes[res].rs = 0;
nodes[res]._sum = nodes[res]._max = 0;
return res;
}
void Update(int p) {
nodes[p]._max = max(nodes[nodes[p].ls]._max, nodes[nodes[p].rs]._max);
nodes[p]._sum = nodes[nodes[p].ls]._sum + nodes[nodes[p].rs]._sum;
}
void Modify(int& p, int l, int r, int x, int v) {
if (p == 0) p = newnode();
if (l == r) {
nodes[p]._max = v;
nodes[p]._sum = v;
return;
}
int mid = (l + r) >> 1;
if (mid >= x) {
if (nodes[p].ls == 0) nodes[p].ls = newnode();
Modify(nodes[p].ls, l, mid, x, v);
} else {
if (nodes[p].rs == 0) nodes[p].rs = newnode();
Modify(nodes[p].rs, mid + 1, r, x, v);
}
Update(p);
}
int Query_Max(int p, int l, int r, int x, int y) {
if (l > y || r < x || p == 0) return 0;
if (l >= x && r <= y) return nodes[p]._max;
int mid = (l + r) >> 1, res = 0;
if (mid >= x) res = max(res, Query_Max(nodes[p].ls, l, mid, x, y));
if (mid < y) res = max(res, Query_Max(nodes[p].rs, mid + 1, r, x, y));
return res;
}
int Query_Sum(int p, int l, int r, int x, int y) {
if (l > y || r < x || p == 0) return 0;
if (l >= x && r <= y) return nodes[p]._sum;
int mid = (l + r) >> 1, res = 0;
if (mid >= x) res += Query_Sum(nodes[p].ls, l, mid, x, y);
if (mid < y) res += Query_Sum(nodes[p].rs, mid + 1, r, x, y);
return res;
}
int Query_Path_Max(int x, int y) {
int res = 0, rt = root[fai[x]];
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
res = max(res, Query_Max(rt, 1, n, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return max(res, Query_Max(rt, 1, n, dfn[x], dfn[y]));
}
int Query_Path_Sum(int x, int y) {
int res = 0, rt = root[fai[x]];
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
res += Query_Sum(rt, 1, n, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return res + Query_Sum(rt, 1, n, dfn[x], dfn[y]);
}
void Operation1(int x, int c) {
Modify(root[fai[x]], 1, n, dfn[x], 0);
fai[x] = c;
Modify(root[c], 1, n, dfn[x], lev[x]);
}
void Operation2(int x, int w) {
lev[x] = w;
Modify(root[fai[x]], 1, n, dfn[x], lev[x]);
}
void Operation3(int x, int y) {
printf("%d\n", Query_Path_Sum(x, y));
}
void Operation4(int x, int y) {
printf("%d\n", Query_Path_Max(x, y));
}
signed main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(lev[i], fai[i]);
for (int i = 1, x, y; i < n; ++i) {
read(x, y);
Graph[x].push_back(y);
Graph[y].push_back(x);
}
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; ++i) Modify(root[fai[i]], 1, n, dfn[i], lev[i]);
for (int i = 0; i < m; ++i) {
char str[5];
scanf("%s", str);
if (str[1] == 'C') {
int x, c;
scanf("%d %d", &x, &c);
Operation1(x, c);
} else if (str[1] == 'W') {
int x, w;
scanf("%d %d", &x, &w);
Operation2(x, w);
} else if(str[1] == 'S') {
int x, y;
scanf("%d %d", &x, &y);
Operation3(x, y);
} else {
int x, y;
scanf("%d %d", &x, &y);
Operation4(x, y);
}
}
return 0;
}48. P5309 [Ynoi2011]初始化
Mayuri 有 $n$ 颗星星，每颗星星都有一个明亮度 $A_{i}$ 。Mayuri 时常想知道一个区间 $[l,r]$ 内所有星星的明亮度的总和是多少。但是星星是会眨眼的，所以星星的明亮度是会变化的。有的时候，下标为 $y,y+x,y+2x,y+3x,\ldots,y+kx$ 的星星的明亮度会增加 $z$。保证 $y\leq x$。
Mayuri 不怎么会数学，请回答她的询问。答案要对 $10^{9}+7$ 取模。
不愧是Ynoi，卡了好久的常数
我做的第一道Ynoi题！
好了我先概括下题目：
*操作$1$：将整个序列中下标$\%x$等于$y$的元素加上$z$。
*操作$2$：查询区间和。
*$2e5$个数，$2e5$个操作。
其实这道题的最大难点在于：$x$可能很小，修改的点很多且不是连续区间。
一个一个改肯定爆炸。
但是如果$x$很大，那么我们一个一个改没有问题。
所以我们可以对x进行分类。
设定一个阈值$lt$。
对于大于$lt$的$x$值，我们暴力修改。（反正个数少~）
对于小于$lt$的$x$值，我们可以用另一种方式来统计。
记录下所有$(x,y)$的操作$1$的$z$的和，用$sum[x][y]$表示。
我们在查询区间值的时候可以先查询暴力修改出来的值，然后统计这些小的修改的贡献。（先看这个区间有多少下标$%\x$等于$y$，然后乘上去再加就好了）
$lt$一般设为$\sqrt n$。（看情况吧）
这就是根号分治了！
根号分治：把一个问题的参数按$\sqrt n$分为两部分，分别设计算法实现。时间复杂度$O(n\sqrt n)$。
但是这样不太能解决这个问题。
因为如果查询一个区间暴力修改的和，我们需要一个数据结构进行查询，否则我们就退回了$O(n^2)$。
而这个数据结构的单点修改必须是$O(1)$的，否则$O(n\log_n\sqrt n)$也是无法通过此题的。
对了！分块！优秀数据结构果然名不虚传
我们用分块来维护暴力修改的区间和。
这个问题解决了，但还有另一个问题。
就是我们统计$sum[x][y]$的贡献的时候，会枚举$x,y$。
而$x,y$都是$\sqrt n$的。
那又回到$O(n^2)$了啊。
但我们稍加观察会发现：
对于每个$x$：$sum[x][y]$乘上的数只会有两个值，而且大的那个是小的那个$+1$。
比如下标序列$3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$对于$x=4$
占位占位占位$3$ $0$ $1$ $2$ $3$ $0$ $1$ $\ \ 2$ $\ 3$ $\ \ 0$
其中$3$出现了$3$次，$2$出现了$2$次，$1$出现了$2$次，$0$出现了$3$次。
我们会发现这是有规律的，其中$3$次的和$2$次的都连成了一个区间。（$0$和$3$其实也是一个连续的区间）
所以我们可以用前缀和优化这个统计过程。
那么前面加上$(x,y)$操作的值的时候，就要把$y$以上的值也加上同样的值，以保持前缀和。单次操作变为$O(n\sqrt n)$。
统计时，先算出较小的那个次数是多少。
然后我们用整个$sum[x][x-1]$来乘上它。接着计算多的那个次数的区间。
那肯定是从$begin\%x$到$end\%x$了！
因为从$end\%x$再到下一个$begin\%x$都没有加上最后一个1。
但是这是有例外的，如果区间长度刚好被x整除，那么我们会多算一个$sum[x][x-1]$。
例外？就是拿来特判的嘛~
那么我们就只用枚举$x$了，时间复杂度最后为$O(n\sqrt n)$。
快乐卡常~$233.cpp$太长我就不放了
代码：
//使用的卡常：少用long long,减法优化模运算，读优输优。
#include<cstdio>
#include<algorithm>
using namespace std;
const int cube=500,mod=1e9+7,cude=200;//这里我数列分块设的500个元素一个块，阈值设的是200。
int n,m,belong[200010],op,opa,opb,opc,sum[610],a[200010],sumar[610][610];//sum是数列分块统计和，sumar[x][y]表示下标%x为y的元素加上的值的前缀和
void read(int &hhh)
{
int x=0;
char c=getchar();
while((c<'0')|(c>'9')&&c^'-') c=getchar();
if(c^'-') x=c^'0';
char d=getchar();
while((d<='9')&(d>='0'))
{
x=(x<<1)+(x<<3)+(d^'0');
d=getchar();
}
if(c^'-') hhh=x;
else hhh=-x;
}
void readlong(long long &hhh)
{
long long x=0;
char c=getchar();
while((c<'0')|(c>'9')&&c^'-') c=getchar();
if(c^'-') x=c^'0';
char d=getchar();
while((d<='9')&(d>='0'))
{
x=(x<<1)+(x<<3)+(d^'0');
d=getchar();
}
if(c^'-') hhh=x;
else hhh=-x;
}
void writinglong(long long x)
{
if(!x) return;
writinglong(x/10);
putchar((x%10)+'0');
}
void writelong(long long x)
{
if(x<0)
{
putchar('-');
x=-x;
}
else if(!x)
{
putchar('0');
putchar('\n');
return;
}
writinglong(x);
putchar('\n');
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;++i)
{
read(a[i]);
if(a[i]==mod) a[i]=0;//因为后面是用减法优化的模运算，所以要先处理到mod范围之内
belong[i]=(i-1)/cube+1;
sum[belong[i]]+=a[i];
if(sum[belong[i]]>=mod) sum[belong[i]]-=mod;
}
for(int i=1;i<=m;++i)
{
read(op);
read(opa);
read(opb);
if(op==1)
{
read(opc);
if(opc==mod||opc==0) continue;//加上的值就等于mod或者0，加了跟没加一样，浪费时间
if(opa<=cude)
{
if(opb==opa) opb=0;//题目描述中y==x和y==0是同样效果
for(int j=opb;j<opa;++j)
{
sumar[opa][j]+=opc;//累加前缀和
if(sumar[opa][j]>=mod) sumar[opa][j]-=mod;
}
}
else
{
for(int j=opb;j<=n;j+=opa)//暴力修改
{
a[j]+=opc;
if(a[j]>=mod) a[j]-=mod;
sum[belong[j]]+=opc;
if(sum[belong[j]]>=mod) sum[belong[j]]-=mod;
}
}
}
else
{
int ans=0;
if(opb-opa+1<=2*cube)//
{
for(int j=opa;j<=opb;++j)
{
ans+=a[j];
if(ans>=mod) ans-=mod;
}
}
else
{
int begin=(opa+cube-2)/cube+1;
int end=opb/cube;
for(int j=begin;j<=end;++j)
{
ans+=sum[j];
if(ans>=mod) ans-=mod;
}
for(int j=(begin-1)*cube;j>=opa;--j)
{
ans+=a[j];
if(ans>=mod) ans-=mod;
}
for(int j=end*cube+1;j<=opb;++j)
{
ans+=a[j];
if(ans>=mod) ans-=mod;
}
}//分块统计暴力加出来的和
long long exans=ans;//这边有乘法必须开long long了
for(int j=1;j<=cude;++j)//枚举x
{
int modea=opa%j;
int modeb=opb%j;
long long less=(opb-opa+1)/j;//少的区间那个的次数
if(less*j==opb-opa+1) exans+=(less*sumar[j][j-1]);//我的特判~
else if(modea<=modeb) exans+=(less*sumar[j][j-1]+sumar[j][modeb]-(modea?sumar[j][modea-1]:0));//该情况中区间连续，直接加
else exans+=(less*sumar[j][j-1]+sumar[j][j-1]-sumar[j][modea-1]+sumar[j][modeb]);//区间被分为前后两个连续部分
exans%=mod;
}
writelong((exans+mod)%mod);//前面可能减出负数
}
}
return 0;
}49.CF383C Propagating tree
Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of $ n $ nodes numbered from $ 1 $ to $ n $ , each node $ i $ having an initial value $ a_{i} $ . The root of the tree is node $ 1 $ .
This tree has a special property: when a value $ val $ is added to a value of node $ i $ , the value - $ val $ is added to values of all the children of node $ i $ . Note that when you add value - $ val $ to a child of node $ i $ , you also add -(- $ val $ ) to all children of the child of node $ i $ and so on. Look an example explanation to understand better how it works.
This tree supports two types of queries:
- " $ 1 $ $ x $ $ val $ " — $ val $ is added to the value of node $ x $ ;
- " $ 2 $ $ x $ " — print the current value of node $ x $ .
In order to help Iahub understand the tree better, you must answer $ m $ queries of the preceding type.
题意简述
给你一颗树，让你支持两种操作，一种子树修改，按深度分正负。一种单点查询节点。
题解
首先考虑把整棵树的DFS序整出来。然后我们可以每次递归结束后再记录一个当前的DFS序的值。
即处理出一棵树的子树中的DFS序的最大值和最小值，由于一颗子树里的DFS序一定是连续的，所以我们把这棵树用DFS序拍平到了序列上。
考虑修改操作没有限制，就是直接更新子树，那么我们可以用线段树或者树状数组来实现区间更新。
由于这个修改操作有限制，要根据修改的节点的深度分类为加或者减。所以我们可以维护两颗线段树/树状数组，一颗加，一颗减。
查询的时候我们就可以直接先查询维护加的线段树/树状数组然后减。
线段树太长，由于查询是单点操作，我们可以把序列差分，用树状数组两次单点修改，查询就两次前缀和即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int Maxn = 2e5 + 5;
int n, m, tot, val [ Maxn ], fwt [ 2 ][ Maxn * 2 + 5 ], dfn [ Maxn ], fywf [ Maxn ], Lp [ Maxn ], Rp [ Maxn ];
vector < int > Graph [ Maxn ];
void dfs ( int x, int fa, int k )
{
Lp [ x ] = ++ tot;
fywf [ x ] = k;
for ( unsigned i = 0; i < Graph [ x ].size ( ); ++ i )
{
int y = Graph [ x ][ i ];
if ( y == fa ) continue;
dfs ( y, x, k ^ 1 );
}
Rp [ x ] = tot;
}
void Modify ( int x, int v, int p )
{
for ( ; x <= n * 2; x += x & -x )
fwt [ p ][ x ] += v;
}
int Query ( int x, int p )
{
int res = 0;
for ( ; x; x -= x & -x )
res += fwt [ p ][ x ];
return res;
}
signed main()
{
scanf ( "%d %d", &n, &m );
for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &val [ i ] );
for (int i = 1, x, y; i < n; ++ i) {
scanf ( "%d %d", &x, &y );
Graph [ x ].push_back ( y );
Graph [ y ].push_back ( x );
}
dfs ( 1, 0, 0 );
for ( int i = 0, t, x, v; i < m; ++ i )
{
scanf ( "%d %d", &t, &x );
if ( t == 1 )
{
scanf ( "%d", &v );
Modify ( Lp [ x ], v, fywf [ x ] );
Modify ( Rp [ x ] + 1, -v, fywf [ x ] );
}
else
{
printf ( "%d\n", val [ x ] + Query ( Lp [ x ], fywf [ x ] ) - Query ( Lp [ x ], fywf [ x ] ^ 1 ) );
}
}
return 0;
}50.P5072 [Ynoi2015]盼君勿忘
珂朵莉给了你一个序列，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod\ p$。
题意简述
不看前面的废话就是题意简述。
题解
这是数据结构一百题的第50题（一半了哦）的纪念题解。
无修改操作，基本确定大方向莫队。
考虑查询的问题，我们可以转化一下。即求区间内每个数出现的次数。
一个区间 $[l,r]$ 的子序列数量为：
$$\sum_{i=0}^{r-l+1}C^{i}_{r-l+1}=2^{r-l+1}$$
比如一个数在区间 $[l,r]$ 出现了 $k$ 次，那么一共有 $2^{r-l+1-k}$ 个子序列不包含这个数。这个很好理解，从组合数的意义可知。那么就有 $2^{r-l+1}-2^{r-l+1-k}$ 个子序列包含了这个数。
那么我们就可以用莫队维护区间中出现了 $k$ 次的所有数的和，然后乘上一个 $2^{r-l+1}-2^{r-l+1-k}$ 就是它的贡献了。
问题又来了：每次询问的模数是不确定的，我们需要每次都需要 $\Theta(n)$ 处理一遍2的幂。
有没有什么方法能把处理这个东西的复杂度降到 $\Theta(\sqrt{n})$ 或以下呢？
对此SyadouHayami表示我们可以打个高精。
方法是有的。
我们可以每次询问都处理出 $2^{1},2^{2},\cdots,2^{\sqrt{n}}$ ，以及 $2^{2\sqrt{n}},2^{3\sqrt{n}},\cdots,2^{n}$，都只需要 $\Theta(\sqrt{n})$。当然，都是在模 $p$ 的意义下的。我们分别记为pow1和pow2。
那么 $2^{x}\operatorname{mod}p=(pow1_{x\operatorname{mod}\sqrt{n}}\times pow2_{\lfloor x\div\sqrt{n}\rfloor})\operatorname{mod}p$。
于是就解决问题了。
我的代码遇到了一下两个玄学问题，贴出来给同样情况的人看看：
- 链表部分的
prev和next如果放在结构体里会T。 pow1,pow2,sum,cnt几个数组的定义如果放在最开头和isa以及ans两个数组一起会RE。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int Maxn = 1e5 + 10;
const int Size = 320;
int n, m, isa[ Maxn ], ans[ Maxn ];
struct Query_Node
{
int l, r, p, id, pos;
} Q[ Maxn ];
struct Linked_List
{
int tot, prev[ Maxn ], next[ Maxn ];
Linked_List( ) { tot = 0; }
void insert( int x )
{
next[ tot ] = x;
prev[ x ] = tot;
tot = x;
}
void erase( int x )
{
if( tot == x ) tot = prev[ x ];
else
{
next[ prev[ x ] ] = next[ x ];
prev[ next[ x ] ] = prev[ x ];
}
prev[ x ] = next[ x ] = 0;
}
} llt;
bool cmp( Query_Node rhs, Query_Node shr )
{
if( rhs.pos != shr.pos ) return rhs.l < shr.l;
else return rhs.r < shr.r;
}
int pow1[ Maxn ], pow2[ Maxn ];
void Pare_Two( int p )
{
pow1[ 0 ] = pow2[ 0 ] = 1;
for( int i = 1; i <= Size; ++ i ) pow1[ i ] = 1ll * 2 * pow1[ i - 1 ] % p;
for( int i = 1; i <= Size; ++ i ) pow2[ i ] = 1ll * pow1[ Size ] * pow2[ i - 1 ] % p;
}
int Get_Two( int x, int p )
{
return 1ll * pow1[ x % Size ] * pow2[ x / Size ] % p;
}
int sum[ Maxn ], cnt[ Maxn ];
void Make_Cont( int x, int f )
{
int pos = isa[ x ];
sum[ cnt[ pos ] ] -= pos;
if ( ! sum[ cnt[ pos ] ] ) llt.erase( cnt[ pos ] );
if( f == 1 ) ++cnt[ pos ];
else --cnt[ pos ];
if ( ! sum[ cnt[ pos ] ] ) llt.insert( cnt[ pos ] );
sum[ cnt[ pos ] ] += pos;
}
void Contribute( )
{
int l = 1, r = 0;
for( int i = 1; i <= m; ++ i )
{
Pare_Two( Q[ i ].p );
while( l > Q[ i ].l ) Make_Cont( --l, 1 );
while( l < Q[ i ].l ) Make_Cont( l++, 0 );
while( r > Q[ i ].r ) Make_Cont( r--, 0 );
while( r < Q[ i ].r ) Make_Cont( ++r, 1 );
for( int s = llt.next[ 0 ]; s; s = llt.next[ s ] )
{
int val = 1ll * sum[ s ] * ( Get_Two( r - l + 1, Q[ i ].p ) - Get_Two( r - l + 1 - s, Q[ i ].p ) + Q[ i ].p ) % Q[ i ].p;
ans[ Q[ i ].id ] += val;
ans[ Q[ i ].id ] %= Q[ i ].p;
}
}
}
signed main( )
{
scanf( "%d %d", &n, &m );
for( int i = 1; i <= n; ++ i ) scanf( "%d", &isa[ i ] );
for( int i = 1; i <= m; ++ i )
{
int l, r, p;
scanf( "%d %d %d", &l, &r, &p );
Q[ i ].l = l, Q[ i ].r = r;
Q[ i ].p = p, Q[ i ].id = i;
Q[ i ].pos = l / Size;
}
sort( Q + 1, Q + 1 + m, cmp );
Contribute( );
for( int i = 1; i <= m; ++ i )
printf( "%d\n", ans[ i ] );
return 0;
}Ds100p -「数据结构百题」31~40
31.P2163 [SHOI2007]园丁的烦恼]
很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。
有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”
“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。
“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”
“是的，显然这是一道经典的动态规划题，早在N元4002年我们就已经发现了其中的奥秘了，陛下”。
“该死的，你究竟是什么来头？”
“陛下息怒，干我们的这行经常莫名其妙地被问到和OI有关的题目，我也是为了预防万一啊！” 王者的尊严受到了伤害，这是不可容忍的。
看来一般的难题是难不倒这位园丁的，国王最后打算用车轮战来消耗他的实力： “年轻人，在我的花园里的每一棵树可以用一个整数坐标来表示，一会儿，我的骑士们会来轮番询问你某一个矩阵内有多少树，如果你不能立即答对，你就准备走人吧！”说完，国王气呼呼地先走了。
这下轮到园丁傻眼了，他没有准备过这样的问题。所幸的是，作为“全国园丁保护联盟”的会长——你，可以成为他的最后一根救命稻草。
这道题拿到一看，第一个想法是二维树状数组。
单点修改，区间查询。
很标准的模板题嘛
这个数据范围可不模板……
就算离散化之后还剩$500000*500000$
连数组都开不下。
所以我们要寻找新的做法。
我们可以看到，所有的询问都会在修改的后面。
所以整个问题是静态的。
那么我们可以使用主席树来解决这个问题。
主席树第$i$个版本统计横坐标为$1-i$的所有树木的纵坐标在权值线段树上的体现。
这个权值线段树维护每个值域有多少个元素。
那么我们就可以在离散化后按照横坐标顺序插入。
查询时利用查分。只需要查询第$xr$个版本时和第$xl-1$个版本时$yl$到$yr$这个区间里有的元素个数，再相减就能得到答案了。
代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,root[1500010],s,e,tot;
struct tree
{
int x,y;
}tre[500010];
struct query
{
int X1,X2,Y1,Y2;
}q[500010];
struct node
{
int l,r,num;
}nodes[50000010];
vector<int> pril,prih,inslist[1500010];
void ins(int l,int r,int pre,int &now,int pos)
{
now=++tot;
nodes[now]=nodes[pre];
++nodes[now].num;
if(l^r)
{
int mid=(l+r)>>1;
if(pos<=mid) ins(l,mid,nodes[pre].l,nodes[now].l,pos);
else ins(mid+1,r,nodes[pre].r,nodes[now].r,pos);
}
}
int find(int l,int r,int v1,int v2,int fr,int ba)
{
if(l>ba||r<fr) return 0;
if(l>=fr&&r<=ba) return nodes[v2].num-nodes[v1].num;
int mid=(l+r)>>1;
return find(l,mid,nodes[v1].l,nodes[v2].l,fr,ba)+find(mid+1,r,nodes[v1].r,nodes[v2].r,fr,ba);
}
void read(int &hhh)
{
int x=0;
char c=getchar();
while((c<'0')|(c>'9')&&c^'-') c=getchar();
if(c^'-') x=c^'0';
char d=getchar();
while((d<='9')&(d>='0'))
{
x=(x<<1)+(x<<3)+(d^'0');
d=getchar();
}
if(c^'-') hhh=x;
else hhh=-x;
}
void writing(int x)
{
if(!x) return;
writing(x/10);
putchar((x%10)+'0');
}
void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
else if(!x)
{
putchar('0');
putchar('\n');
return;
}
writing(x);
putchar('\n');
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;++i)
{
read(tre[i].x);
read(tre[i].y);
pril.push_back(tre[i].x);
prih.push_back(tre[i].y);
}
for(int i=1;i<=m;++i)
{
read(q[i].X1);
read(q[i].Y1);
read(q[i].X2);
read(q[i].Y2);
--q[i].X1;
pril.push_back(q[i].X1);
prih.push_back(q[i].Y1);
pril.push_back(q[i].X2);
prih.push_back(q[i].Y2);
}
sort(pril.begin(),pril.end());
sort(prih.begin(),prih.end());
pril.erase(unique(pril.begin(),pril.end()),pril.end());
prih.erase(unique(prih.begin(),prih.end()),prih.end());
s=prih.size();
e=pril.size();
for(int i=1;i<=n;++i)
{
tre[i].x=lower_bound(pril.begin(),pril.end(),tre[i].x)-pril.begin()+1;
tre[i].y=lower_bound(prih.begin(),prih.end(),tre[i].y)-prih.begin()+1;
inslist[tre[i].x].push_back(tre[i].y);
}
for(int i=1;i<=m;++i)
{
q[i].X1=lower_bound(pril.begin(),pril.end(),q[i].X1)-pril.begin()+1;
q[i].Y1=lower_bound(prih.begin(),prih.end(),q[i].Y1)-prih.begin()+1;
q[i].X2=lower_bound(pril.begin(),pril.end(),q[i].X2)-pril.begin()+1;
q[i].Y2=lower_bound(prih.begin(),prih.end(),q[i].Y2)-prih.begin()+1;
}
for(int i=1;i<=e;++i)
{
root[i]=root[i-1];
int WHILEMAX=inslist[i].size();
for(int j=0;j^WHILEMAX;++j) ins(1,s,root[i],root[i],inslist[i][j]);
}
for(int i=1;i<=m;++i) write(find(1,s,root[q[i].X1],root[q[i].X2],q[i].Y1,q[i].Y2));
return 0;
}32.P2471 [SCOI2007]降雨量
我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y<Z<X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。
这道题要求查询一个数是否是继另一个数后的最大值。
然而中间有很多数是未知的。
要判断这个结论一定成立，我们要知道中间的数是不是都知道。
那我们是不是要把所有的数都放进线段树里呢？
肯定不行，因为年份的范围是$1e9$。
那我们怎么离散化呢？
这里我们只用把与每个年份相邻的两个年份也加进来就好了，再顺便把查询的端点和往内一个数也加进来，不然找端点的时候容易锅……
因为如果查询时这里没有数，那么肯定就被查到了。
如果这里有，那么这里的这个数就会又把它两边的数加进来。一直到要查询到的那个数为止。
那么我们应该怎么判断呢？
这里就要分类讨论了：查询为$(p,q)$
$1.p > q$：肯定不成立，他们的位置都不对，$p$根本不在$q$前面。
$2.p=q$：显然成立。
$3.$继续分类。
$\ \ \ \ \ $$1).$两个端点都已知。
$\ \ \ \ \ \ \ \ \ \ $$1>.$$p$的降雨量小于$q$：肯定不对，不符合定义。
$\ \ \ \ \ \ \ \ \ \ $$2>.$如果$p,q$中间有数比$q$的降雨量大或等于：也不符合定义，不对。
$\ \ \ \ \ \ \ \ \ \ $$3>.$如果$p,q$中间有数未知:那么我们无法确定这些未知的数是否小于$q$的降雨量，输出也许。
$\ \ \ \ \ \ \ \ \ \ $$4>.$以上条件均不满足：说明满足了所有条件，是对的。
$\ \ \ \ \ $$2).$知道$p$的降雨量。
$\ \ \ \ \ \ \ \ \ \ $$1>.$如果$p,q$中间有数大于$p$的降雨量或等于：不符合定义，不对。
$\ \ \ \ \ \ \ \ \ \ $$2>.$否则无论中间是否全部已知，由于$q$未知，都不能确定。
$\ \ \ \ \ $$3).$知道$q$的降雨量。
$\ \ \ \ \ \ \ \ \ \ $$1>.$如果$p,q$中间有数大于$q$的降雨量或等于：不符合定义，不对。
$\ \ \ \ \ \ \ \ \ \ $$2>.$否则无论中间是否全部已知，由于$p$未知，都不能确定。
$\ \ \ \ \ $$4).$两个都未知：无论中间是否全部已知，由于不能确定中间的数是否小于他们，所以输出也许。
关于判断中间是否有数大于某数，我们需要查询中间的最大值。
关于判断中间是否有数未知，我们需要查询区间里有多少数。
所以我们要开两棵线段树，一棵记录区间最大值，一棵记录区间里的元素个数。
代码：
#include<map>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> pri;
map<int,int> mp;
int n,m,s,y[50010],r[50010],p[10010],q[10010],siz[1000010],nodes[1000010];
int getID(int val)
{
return lower_bound(pri.begin(),pri.end(),val)-pri.begin()+1;
}
void ins(int l,int r,int x,int pos,int val)
{
++siz[x];
if(l==r) nodes[x]=val;
else
{
int mid=(l+r)>>1;
if(pos<=mid) ins(l,mid,x<<1,pos,val);
else ins(mid+1,r,x<<1|1,pos,val);
nodes[x]=max(nodes[x<<1],nodes[x<<1|1]);
}
}
int findsiz(int l,int r,int x,int fr,int ba)
{
if(l>ba||r<fr) return 0;
if(l>=fr&&r<=ba) return siz[x];
else
{
int mid=(l+r)>>1;
return findsiz(l,mid,x<<1,fr,ba)+findsiz(mid+1,r,x<<1|1,fr,ba);
}
}
int findmax(int l,int r,int x,int fr,int ba)
{
if(l>ba||r<fr) return 0;
if(l>=fr&&r<=ba) return nodes[x];
else
{
int mid=(l+r)>>1;
return max(findmax(l,mid,x<<1,fr,ba),findmax(mid+1,r,x<<1|1,fr,ba));
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&y[i],&r[i]);
pri.push_back(y[i]-1);
pri.push_back(y[i]);
pri.push_back(y[i]+1);
mp[y[i]]=r[i];
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d %d",&p[i],&q[i]);
pri.push_back(p[i]);
pri.push_back(p[i]+1);
pri.push_back(q[i]);
pri.push_back(q[i]-1);
}
sort(pri.begin(),pri.end());
pri.erase(unique(pri.begin(),pri.end()),pri.end());
s=pri.size();
for(int i=1;i<=n;++i) ins(1,s,1,getID(y[i]),r[i]);
for(int i=1;i<=m;++i)
{
int L=getID(p[i]);
int R=getID(q[i]);
if(p[i]>q[i]) printf("false\n");
else if(p[i]==q[i]) printf("true\n");
else if(mp[p[i]]&&mp[q[i]])
{
if(mp[p[i]]<mp[q[i]]) printf("false\n");
else
{
if(findmax(1,s,1,L+1,R-1)<mp[q[i]])
{
if(findsiz(1,s,1,L,R)==R-L+1) printf("true\n");
else printf("maybe\n");
}
else printf("false\n");
}
}
else if(mp[p[i]])
{
if(findmax(1,s,1,L+1,R)>=mp[p[i]]) printf("false\n");
else printf("maybe\n");
}
else if(mp[q[i]])
{
if(findmax(1,s,1,L,R-1)>=mp[q[i]]) printf("false\n");
else printf("maybe\n");
}
else printf("maybe\n");
}
return 0;
}33.P2824 [HEOI2016/TJOI2016]排序
在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。
这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：
0 l r表示将区间 $[l,r]$ 的数字升序排序1 l r表示将区间 $[l,r]$ 的数字降序排序
注意，这里是对下标在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。
这道题很有意思，需要一定的技巧。
首先我们知道，对于一个长度为 $n$ 整数序列排序需要 $\Theta(n\log n)$ 的时间。
但是，如果我们把序列中的数字从所有的数转移到0和1两个数上，是不是就容易很多呢？
对于一个01串升序排序显然只需要 $\Theta(n)$ 的时间。我们只需要统计出序列中所以1的个数 $cnt$。
然后把 $A_{i},i\in [1,n-cnt]$ 改为零，把 $A_{i},i\in [n-cnt+1,n]$ 改为1即可。
降序排序则完全同理。
不仅如此，我们还可以把时间从 $\Theta(n)$ 降到 $\Theta(\log n)$。
我们可以把统计区间中1的个数看作区间求和，那么我们就可以用线段树来维护区间赋值和区间求和的操作，复杂度 $\Theta(\log n)$。
好，接下来我们思考一个问题——如何把一个普通的序列转化为01序列呢？我们可以按大小来划分。
假设我们现在正在二分，那么我们不妨把所有大于等于 $mid$ 的数置为1，否则置为0。这样整个序列就变成了一个01序列。
排序后判断第 $q$ 个位置是不是1就行了。
这里还有一个问题——为什么这个二分是满足单调性的呢？
其实这个问题很简单，就留给大家吧）））
#pragma GCC diagnostic error "-std=c++11"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#ifndef ONLINE_JUDGE
#define gc() getchar()
#else
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#endif
#define is_number (ch >= '0' && ch <= '9')
template < typename Type >
void read(Type& a) {
a = 0; bool f = 0; char ch;
while (!(ch = gc(), is_number)) if (ch == '-') f = 1;
while (is_number) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = gc();
a = (f ? -a : a);
}
template < typename Type, typename... Args >
void read(Type& t, Args&... args) {
read(t), read(args...);
}
#define ls (k << 1)
#define rs (k << 1 | 1)
// #define mid ((l + r) >> 1)
const int MAXN = 1e5 + 5;
int nodes[MAXN << 2];
int marks[MAXN << 2];
int ints[MAXN], bit[MAXN];
int n, m, q;
struct QueryNode {
int l, r;
int type;
QueryNode(){}
QueryNode(int L, int R, int T) : l(L), r(R), type(T) {}
} asks[MAXN];
void pushdown(int k, int l, int r) {
if (~marks[k]) {
int mid = (l + r) >> 1;
nodes[ls] = (mid - l + 1) * marks[k];
marks[ls] = marks[k];
nodes[rs] = (r - mid) * marks[k];
marks[rs] = marks[k];
marks[k] = -1;
}
}
void construct(int k, int l, int r) {
int mid = ((l + r) >> 1);
if (l ^ r) {
construct(ls, l, mid);
construct(rs, mid + 1, r);
nodes[k] = nodes[ls] + nodes[rs];
}
else
nodes[k] = bit[l];
}
void update(int k, int l, int r, int x, int y, int v) {
int mid = ((l + r) >> 1);
if (l > y || r < x) return ;
if (l >= x && r <= y) nodes[k] = (r - l + 1) * v, marks[k] = v;
else {
pushdown(k, l, r);
if (mid >= x) update(ls, l, mid, x, y, v);
if (mid < y) update(rs, mid + 1, r, x, y, v);
nodes[k] = nodes[ls] + nodes[rs];
}
}
int queryf(int k, int l, int r, int x, int y) {
int mid = ((l + r) >> 1);
pushdown(k, l, r);
if (l > y || r < x) return 0;
else if (l >= x && r <= y) return nodes[k];
else return queryf(ls, l, mid, x, y) + queryf(rs, mid + 1, r, x, y);
}
bool check(int x) {
for (int i = 1; i <= n; ++i) bit[i] = (ints[i] >= x);
memset(marks, -1, sizeof marks);
memset(nodes, 0, sizeof nodes);
construct(1, 1, n);
for (int i = 1; i <= m; ++i) {
int sum = queryf(1, 1, n, asks[i].l, asks[i].r);
if (asks[i].type == 1) update(1, 1, n, asks[i].l, asks[i].l + sum - 1, 1), update(1, 1, n, asks[i].l + sum, asks[i].r, 0);
else update(1, 1, n, asks[i].l, asks[i].r - sum, 0), update(1, 1, n, asks[i].r - sum + 1, asks[i].r, 1);
}
return queryf(1, 1, n, q, q);
}
signed main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(ints[i]);
for (int i = 1; i <= m; ++i) read(asks[i].type, asks[i].l, asks[i].r);
read(q);
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = ((l + r) >> 1);
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
printf("%d\n", ans);
return 0;
}34.P1712 [NOI2016]区间
在数轴上有 $N$ 个闭区间 $[l_1,r_1],[l_2,r_2],...,[l_n,r_n]$ 。现在要从中选出 $M$ 个区间，使得这 $M$ 个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$ ，使得对于每一个被选中的区间$[l_i,r_i]$ ，都有 $l_i≤x≤r_i$ 。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间$[l_i,r_i]$ 的长度定义为$r_i-l_i$ ，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 $-1$ 。
题意简述
题意已经很清楚了，就不再说了
题解
我们首先考虑怎么去选择这 $M$ 个区间才能使得最终的花费最小。
不难想到我们需要尽量选择 长度尽量靠近 的 $M$ 个区间，换句话说就是我们需要按照区间的长度进行排序。
原因很显然，我们如果选择的区间的长度不靠近，那么就会造成最小的区间长度变小，最大的区间长度变大。然而答案就是长度最大的区间和长度最小的区间，所以我们需要让这两个区间的长度尽量靠近。
排完序后我们就依次把每个区间加入到答案所在的集合里。
具体来说就是维护一个数组 $A$，每当我们加入一个区间 $[l_{i},r_{i}]$，就令 $A_{l_{i}},A_{l_{i}+1},\cdots,A_{r_{i}}$ 全部加一。如果存在某一个 $A_{p}$ 使得 $M\le A_{p}$，我们就更新答案，并且删除最先加入进来的区间，也就是令 $A_{l_{i}},A_{l_{i}+1},\cdots,A_{r_{i}}$ 全部减一。
一些细节：
- 要离散化（废话
- 线段树开8倍（每个区间有两个端点
- 没了
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int SIZE = 500000 + 5;
int MAX[SIZE << 3];
int mark[SIZE << 3];
vector < int > disc;
int n, m, holyans = -1;
struct interval {
int l, r;
int len;
interval(){}
interval(int L, int R, int S) : l(L), r(R), len(S){}
bool operator < (const interval& rhs) const {
return len < rhs.len;
}
} seg[SIZE];
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
#define pushdown(k) \
if (mark[k]) { \
MAX[ls] += mark[k]; \
MAX[rs] += mark[k]; \
mark[ls] += mark[k]; \
mark[rs] += mark[k]; \
mark[k] = 0; \
}
#define pushup(k) MAX[k] = max(MAX[ls], MAX[rs])
#define GetID(x) (lower_bound(disc.begin(), disc.end(), x) - disc.begin() + 1)
void modify(int k, int l, int r, int x, int y, int v) {
if (l >= x && r <= y) mark[k] += v, MAX[k] += v;
else {
pushdown(k);
if (mid >= x) modify(ls, l, mid, x, y, v);
if (mid < y) modify(rs, mid + 1, r, x, y, v);
pushup(k);
}
}
void discretization() {
for (int i = 1; i <= n; ++i) disc.push_back(seg[i].l), disc.push_back(seg[i].r);
sort(disc.begin(), disc.end());
sort(seg + 1, seg + 1 + n);
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (int i = 1; i <= n; ++i) seg[i].l = GetID(seg[i].l), seg[i].r = GetID(seg[i].r);
}
signed main() {
scanf("%d %d", &n, &m);
for (int i = 1, x, y; i <= n; ++i) scanf("%d %d", &x, &y), seg[i] = interval(x, y, y - x + 1);
discretization();
int size = disc.size();
int max_id = n;
for (int i = n; i >= 1; --i) {
while (MAX[1] >= m && max_id > i) {
modify(1, 1, size, seg[max_id].l, seg[max_id].r, -1);
--max_id;
if (MAX[1] >= m) {
if (~holyans) holyans = min(holyans, seg[max_id].len - seg[i].len);
else holyans = seg[max_id].len - seg[i].len;
}
}
modify(1, 1, size, seg[i].l, seg[i].r, 1);
if (MAX[1] >= m) {
if (~holyans) holyans = min(holyans, seg[max_id].len - seg[i].len);
else holyans = seg[max_id].len - seg[i].len;
}
}
printf("%d\n", holyans);
return 0;
}35.P5524 [Ynoi2012]NOIP2015洋溢着希望
给出一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，进行 $m$ 次操作，操作分为两类。
操作 $1$：给出 $l,r,v$，将 $a_l,a_{l+1},\ldots,a_r$ 分别加上 $v$。
操作 $2$：给出 $l,r$，询问 $\sum\limits_{i=l}^{r}\sin(a_i)$。
唯一一道我能做的Ynoi……
修改操作很模板，略。
对于询问，直接维护是不理智的。相信大家都学过三角函数，和差角公式应该很熟悉。
对于这道题我们可以用这两个公式来维护询问：
$$ \sin(\alpha+\beta)=\sin\ \alpha\times\cos\ \beta+\cos\ \alpha\times\sin\ \beta $$
$$ \cos(\alpha+\beta)=\cos\ \alpha\times\cos\ \beta-\sin\ \alpha\times\sin\ \beta $$
这样，我们再维护一个加法标记，就能解决询问了。
挺水的对吧。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 2e5 + 5;
int n, m, integer[MAXN];
long long nodes[MAXN << 2];
double sum_sinx[MAXN << 2];
double sum_cosx[MAXN << 2];
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
void update(int k, double sinx, double cosx) {
double tsum_sinx = sum_sinx[k];
double tsum_cosx = sum_cosx[k];
sum_sinx[k] = tsum_sinx * cosx + tsum_cosx * sinx;
sum_cosx[k] = tsum_cosx * cosx - tsum_sinx * sinx;
}
void pushup(int k) {
sum_sinx[k] = sum_sinx[ls] + sum_sinx[rs];
sum_cosx[k] = sum_cosx[ls] + sum_cosx[rs];
}
void pushdown(int k) {
if (nodes[k]) {
nodes[ls] += nodes[k];
nodes[rs] += nodes[k];
double t_sinx = sin(nodes[k]);
double t_cosx = cos(nodes[k]);
nodes[k] = 0;
update(ls, t_sinx, t_cosx);
update(rs, t_sinx, t_cosx);
}
}
void build(int k, int l, int r) {
if (l ^ r) build(ls, l, mid), build(rs, mid + 1, r), pushup(k);
else sum_sinx[k] = sin(integer[l]), sum_cosx[k] = cos(integer[l]);
}
void modify(int k, int l, int r, int x, int y, int v, double sinx, double cosx) {
if (l >= x && r <= y) update(k, sinx, cosx), nodes[k] += v;
else {
pushdown(k);
if (mid >= x) modify(ls, l, mid, x, y, v, sinx, cosx);
if (mid < y) modify(rs, mid + 1, r, x, y, v, sinx, cosx);
pushup(k);
}
}
double queryf(int k, int l, int r, int x, int y) {
if (l >= x && r <= y) return sum_sinx[k];
else {
pushdown(k);
double res = 0;
if (mid >= x) res += queryf(ls, l, mid, x, y);
if (mid < y) res += queryf(rs, mid + 1, r, x, y);
return res;
}
}
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &integer[i]);
build(1, 1, n);
scanf("%d", &m);
for (int i = 0, opt, x, y, v; i < m; ++i) {
scanf("%d %d %d", &opt, &x, &y);
if (opt == 1) scanf("%d", &v), modify(1, 1, n, x, y, v, sin(v), cos(v));
else printf("%.1lf\n", queryf(1, 1, n, x, y));
}
return 0;
}36.P5335 [THUSC2016]补退选
X 是 T 大的一名老师，每年他都要教授许多学生基础的 C++ 知识。在 T 大，每个学生在每学期的开学前都需要选课，每次选课一共分为三个阶段：预选，正选，补退选；其中「补退选」阶段最忙碌。
在补退选阶段，学生即可以选课，也可以退课。对于X老师来说，在补退选阶段可能发生以下两种事件：
1.一个姓名为 $S$ 的学生选了他的课（姓名将出现在 X 的已选课学生名单中）
2.一个姓名为 $S$ 的学生退了他的课（姓名将从 X 的已选课学生名单中移除）
同时，X 老师对于有哪些学生选了他的课非常关心，所以他会不定时的查询已选课学生名单，每次查询的格式如下：
最早在哪个事件之后，姓名以 S 为前缀的学生数量超过了 vX老师看你骨骼惊奇，所以想用这个问题考考你，你当然不会畏惧，所以勇敢的接下了这个任务。
注意1：学生的姓名可能相同，如果有$p$个姓名相同的学生都选了X老师的课，则他们的姓名将出现在X老师的名单上$p$次。
注意2：只有已经选了课的学生才会退课，如果姓名为$S$的学生退课，则在他退课之前X老师的名单上一定有姓名。
注意3：选课，退课和查询都被定义为「事件」，「事件」的编号从 1 开始
题意简述
给定插入、删除字符串的操作，查询在最早哪一时刻以 $S$ 为前缀的字符串数量超过了某一个值。
题解
字符串+前缀一眼就trie树了嘛。
插入和删除都是常规的trie，可以维护一个sum来统计。
如果某一时刻的sum超过了vector统计的size，那么就push进去。
查询的话就暴力查询。如果在某一个字符的统计少于了 $k$ 那么就不可能了。
总结来说，这是一道比较水而且典型的trie树练习题。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, tot, lastans = 0;
struct TrieNode {
int frie, ch[30];
vector < int > rec;
} trie[N];
void Insert(char str[], int ts) {
int root = 0;
for (int i = 0; str[i]; ++i) {
int now = str[i] - 'a';
if (!trie[root].ch[now]) trie[root].ch[now] = ++tot;
root = trie[root].ch[now];
trie[root].frie++;
if (trie[root].frie > (int)trie[root].rec.size()) trie[root].rec.push_back(ts);
}
}
void Delete(char str[], int ts) {
int root = 0;
for (int i = 0; str[i]; ++i) {
int now = str[i] - 'a';
if (!trie[root].ch[now]) trie[root].ch[now] = ++tot;
root = trie[root].ch[now];
trie[root].frie--;
if (trie[root].frie >= (int)trie[root].rec.size()) trie[root].rec.push_back(ts);
}
}
int Queryf(char str[], long long k) {
int root = 0;
for (int i = 0; str[i]; ++i) {
int now = str[i] - 'a';
root = trie[root].ch[now];
if ((long long)trie[root].rec.size() <= k) return -1;
}
return trie[root].rec[k];
}
signed main() {
scanf("%d", &n);
for (int i = 1, opr, a, b, c; i <= n; ++i) {
char str[N];
scanf("%d %s", &opr, str);
if (opr == 1) Insert(str, i);
else if (opr == 2) Delete(str, i);
else scanf("%d %d %d", &a, &b, &c), printf("%d\n", lastans = Queryf(str, (1LL * a * abs(lastans) + 1LL * b) % (1LL * c)));
}
return 0;
}37.P4309 【[TJOI2013]最长上升子序列】
给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？
Description
动态维护LIS
Solution
这道题正解应该是在平衡树上维护dp。
设 $dp_{i}$ 表示前 $i$ 个数的LIS长度，转移方程显然为：
$$ dp_{i}=max\{dp_{j}+1\} $$
这东西都不知道可以考虑$\ \ \ \ \ \ \ \ \ \ \ $了
然后我们放到维护的节点上即可。
开头说过平衡树对吧，但是这道题的数据过水，vector+bit直接能过，而且跑得飞快，管理如果有心情的话就加强一下吧。
#include <bits/stdc++.h>
const int N = 100000 + 5;
int n, p[N], ans[N], bit[N];
std::vector < int > vec;
void update(int x, int y) {
for (; x <= n; x += x & -x) bit[x] = std::max(bit[x], y);
}
int queryf(int x) {
int res = 0;
for (; x; x -= x & -x) res = std::max(res, bit[x]);
return res;
}
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &p[i]), vec.insert(p[i] + vec.begin(), i);
for (int i = 1; i <= n; ++i) ans[vec[i - 1]] = queryf(vec[i - 1]) + 1, update(vec[i - 1], ans[vec[i - 1]]);
for (int i = 1; i <= n; ++i) ans[i] = std::max(ans[i], ans[i - 1]);
for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
return 0;
}38.CF85D Sum of Medians
一个集合，初始为空。现有三个操作：
1.add：向集合里加入数x，保证加入前集合中没有数x；
2.del：从集合中删除数x，保证删除前集合中有x；
3.sum：询问将集合里的数从小到大排序后，求下标i模5余3的数的和。
现有n次操作，对于每个查询操作，输出答案Description
让你维护一个类似std::set的东西，实现一个支持插入、删除、查询升序排序后的 $\sum_{i=1}^{n}[i\operatorname{mod}5=3]\times A_{i}$ 的不可重集合。
Solution
正解线段树没跑。但是我们看到3S的时限 $10^{5}$ 的数据以及一贯的CF数据。我们有理由认为这道题vector模拟能过（滑稽
然后就真的能过，std::lower_bound查找插入以及删除的位置。查询的话就 $i$ 从2开始（vector下标从0开始，所以要减一），每次 $i=i+5$ 然后累加 $A_{i}$ 即可。
#include <bits/stdc++.h>
std::vector < int > vect;
signed main() {
int n;
scanf("%d", &n);
for (int i = 0, x; i < n; ++i) {
char str[5];
scanf("%s", str);
if (*str == 'a') {
scanf("%d", &x);
vect.insert(std::lower_bound(vect.begin(), vect.end(), x), x);
} else if (*str == 'd') {
scanf("%d", &x);
vect.erase(std::lower_bound(vect.begin(), vect.end(), x));
} else {
long long res = 0;
for (unsigned i = 2; i < vect.size(); i += 5) res += vect[i];
printf("%lld\n", res);
}
}
return 0;
}39.P3620 [APIO/CTSC 2007]数据备份
你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。
已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。
然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼(或总计 2K 个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说，这 2K 个办公楼一定是相异的)。
此外，电信公司需按网络电缆的长度(公里数)收费。因而，你需要选择这 K对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和(总距离)尽可能小。
下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。
上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km―1km = 2km，第 2 条电缆的长度是 6km―4km = 2 km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。
题意简述
给定 $n$ 栋建筑，选出 $k$ 对，使其距离之和最小。
题解
可以想见，这 $k$ 对建筑每对都是相邻的。我们设 $L_{i}=A_{i}-A_{i-1}$，其中 $A_{i}$ 为题目中输入的序列。即 $L$ 为 $A$ 的差分序列。
由于已经被选过的位置不能再次被选，所以如果我们选了 $L_{i}$ 那么 $L_{i+1}$ 和 $L_{i-1}$ 都不能选了。如果我们选了 $L_{i+1}$ 和 $L_{i-1}$ 那么我们也不能选 $L_{i}$ 了。
我们设 $L$ 中的最小值为 $L_{m}$。考虑当前情况的每一个最优解，则只有以下两种情形：
- 选 $L_{m}$
- 选 $L_{m+1}$ 和 $L_{m-1}$
如此我们得到了一个策略：每次选择 $L$ 中的最小值即 $L_{m}$，然后删除 $L_{m},L_{m-1},L_{m+1}$。如果我们选择了 $L_{m+1}+L_{m-1}-L_{m}$ 的话，即删除 $L_{m}$，选择 $L_{m}$。否则即认为选择 $L_{m}$ 是当前的最优策略。
思路来自李煜东的蓝书。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, k, tot, rhs, ans, dis[N], lists[N];
struct ListNode {
struct LinkList {
int prev, next;
int val, id;
} p[N];
void remove(int x) {
p[p[x].prev].next = p[x].next;
p[p[x].next].prev = p[x].prev;
}
} list;
struct HeapNode {
struct Heap {
int val, id;
} h[N];
void upward(int x) {
while (x > 1) {
if (h[x].val < h[x >> 1].val) {
swap(h[x], h[x >> 1]);
swap(list.p[h[x].id].id, list.p[h[x >> 1].id].id);
x >>= 1;
}
else break;
}
}
void downward(int x) {
int s = x << 1;
while (s <= tot) {
if (s < tot && h[s].val > h[s + 1].val) ++s;
if (h[s].val < h[x].val) {
swap(h[s], h[x]);
swap(list.p[h[s].id].id, list.p[h[x].id].id);
x = s;
s = x << 1;
}
else break;
}
}
void remove(int x) {
if (x == --tot + 1) return ;
swap(h[x], h[tot + 1]);
swap(list.p[h[x].id].id, list.p[h[tot + 1].id].id);
upward(x);
downward(x);
}
void extract(int x) {
h[1] = h[n--];
downward(1);
}
int backtop() {
return h[1].val;
}
} heap;
signed main() {
scanf("%d %d %d", &n, &k, &rhs);
for (int i = 1; i < n; ++i) {
int x; scanf("%d", &x);
list.p[i].val = x - rhs;
list.p[i].prev = i - 1;
list.p[i].next = i + 1;
list.p[i].id = ++tot;
rhs = x;
heap.h[tot].val = list.p[i].val;
heap.h[tot].id = i;
heap.upward(tot);
}
for (int i = 1; i <= k; ++i) {
ans += heap.backtop();
if (!list.p[heap.h[1].id].prev || list.p[heap.h[1].id].next == n) {
if (!list.p[heap.h[1].id].prev) {
heap.remove(list.p[list.p[heap.h[1].id].next].id);
list.remove(list.p[heap.h[1].id].next);
}
else {
heap.remove(list.p[list.p[heap.h[1].id].prev].id);
list.remove(list.p[heap.h[1].id].prev);
}
list.remove(heap.h[1].id);
heap.remove(1);
}
else {
int temp = heap.h[1].id;
heap.h[1].val = list.p[list.p[heap.h[1].id].prev].val + list.p[list.p[heap.h[1].id].next].val - list.p[heap.h[1].id].val;
list.p[heap.h[1].id].val = heap.h[1].val;
heap.downward(1);
heap.remove(list.p[list.p[temp].prev].id);
heap.remove(list.p[list.p[temp].next].id);
list.remove(list.p[temp].prev);
list.remove(list.p[temp].next);
}
}
printf("%d\n", ans);
return 0;
}40.P3793 由乃救爷爷
读入三个数n,m,s
你需要srand( s )一下
然后n个数表示a[i]，这个直接调用read函数
然后m个询问，表示区间最大值，询问的区间是l = read() % n + 1 , r = read() % n + 1，注意有可能 l > r
题意简述
给定序列，求每次询问区间的RMQ。
题解
不带修的RMQ我们一般使用的是ST表求。但这道题ST表 $\Theta(n\log n)$ 的空间当场去世。
我们考虑把序列分个块儿。由于查询的区间不一定会完全覆盖完一个块儿，所以我么需要求出每个块儿中的前/后缀最大值，然后用ST表搞出整个块儿的最大值。
但是如果 $l,r$ 在同一个块儿内的话就会出问题，所以当查询区间的两端点在同一个块儿内的时候我们就直接暴力查询。
const int N = 2e7 + 5;
const int SQN = 4500 + 5;
const int LGSQN = 10 + 5;
int n, m, s, block = 7500;
__uint64 f[SQN][LGSQN], a[N];
__uint64 ans, cpy[N], pas[N];
__uint64 get(__uint64 x) {
return (x + block - 1) / block;
}
__uint64 ret(__uint64 l, __uint64 r) {
__uint64 res = a[l];
for (__uint64 i = l; i <= r; ++i) res = max(res, a[i]);
return res;
}
signed main() {
read(n, m, s);
_srand(s);
for (int i = 1, j = 1; i <= n; ++i, j = get(i)) {
a[i] = _read();
f[j][0] = max(a[i], f[j][0]);
}
int mot = get(n);
int fck = log2(mot);
for (int j = 1; j <= fck; ++j)
for (int i = 1; i <= mot - (1 << j) + 1; ++i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (int i = 1; i <= n; ++i)
if (i % block != 1) pas[i] = max(pas[i - 1], a[i]);
else pas[i] = a[i];
for (int i = n; i >= 1; --i)
if (i % block) cpy[i] = max(cpy[i + 1], a[i]);
else cpy[i] = a[i];
for (int i = 0; i < m; ++i) {
__uint64 x = _read() % n + 1;
__uint64 y = _read() % n + 1;
if (x > y) swap(x, y);
__uint64 l = get(x), r = get(y);
__uint64 MAX = max(cpy[x], pas[y]);
if (l == r) ans += ret(x, y);
else if (r - l == 1) ans += MAX;
else {
__uint64 k = log2(r - l - 1);
__uint64 t = max(f[l + 1][k], f[r - (1 << k)][k]);
ans += max(MAX, t);
}
}
write(io_l, ans);
}