matrix

n ∗ m ≤ 5 e 5 , 1 ≤ a i , j ≤ 1 e 9 n*m≤5e5,1≤a_{i,j}≤1e9 n∗m≤5e5,1≤ai,j​≤1e9
一道很妙的题。
首先大家应该都会无脑的 O ( n m 2 ) d p O(nm^2)dp O(nm2)dp，即我们固定左右端点和之间的字符串 S S S，从上往下扫计算每一行的贡献，对于第 i i i行的串 S i S_i Si​，我们设上一个出现的满足 S j = S i S_j=S_i Sj​=Si​的位置为 j j j，那么 S i S_i Si​对答案的贡献就是 ( i − j ) ∗ ( n − i + 1 ) (i-j)*(n-i+1) (i−j)∗(n−i+1)
于是对于每一种串我们可以维护其出现位置的集合 s e t S = { a 0 , a 1 , a 2 , . . , a t } set_S=\{a_0,a_1,a_2,..,a_t\} setS​={a0​,a1​,a2​,..,at​}，其中 a 0 = 0 a_0=0 a0​=0是方便计算的，那么这个串的贡献就是 ∑ i = 1 t ( a i − a i − 1 ) ( n − a i + 1 ) \sum_{i=1}^t(a_i-a_i-1)(n-a_i+1) ∑i=1t​(ai​−ai​−1)(n−ai​+1)
现在的问题变成了如何快速维护这个东西。
考虑先将 l l l强制为 1 1 1，然后按行建立 t r i e trie trie树，对于每个节点维护上面谈到的位置集合，然后可以统计出 l = 1 l=1 l=1时候的答案。
然后当 l → l + 1 l\rightarrow l+1 l→l+1的时候，我们把当前根节点的所有儿子删掉，把所有儿子的儿子启发式合并起来即可。
代码：

#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){static char buf[rlen],*ib,*ob;(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));return ib==ob?-1:*ib++;
}
inline int read(){int ans=0;char ch=gc();while(!isdigit(ch))ch=gc();while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();return ans;
}
typedef long long ll;
const int N=5e5+5;
int n,m,a[N],rt=1,tot=1;
map<int,int>son[N];
set<int>pos[N];
typedef map<int,int>::iterator It;
ll ans=0,sum=0,val[N];
inline void build(int id,int l,int r){for(ri p=rt,v,i=l;i<=r;++i){if(!son[p][a[i]])son[p][a[i]]=++tot,pos[son[p][a[i]]].insert(0),pos[son[p][a[i]]].insert(n+1);pos[v=son[p][a[i]]].insert(id);set<int>::iterator it=pos[v].lower_bound(id);--it,val[v]+=(ll)(id-*it)*(n-id+1);p=v;}
}
inline int merge(int x,int y){if(!x||!y)return x+y;if(pos[x].size()<pos[y].size())swap(x,y);sum-=val[x]+val[y];set<int>::iterator L=pos[y].begin(),R=pos[y].end();++L,--R;for(set<int>::iterator it=L,il,ir;it!=R;++it){pos[x].insert(*it),il=ir=pos[x].lower_bound(*it),--il,++ir;val[x]+=(ll)(*it-*il)*(*ir-*it);}
//	pos[y].clear();sum+=val[x];for(It it=son[y].begin();it!=son[y].end();++it)son[x][it->fi]=merge(son[x][it->fi],it->se);
//	son[y].clear();return x;
}
inline void update(){static int stk[N],top=0;for(It it=son[rt].begin();it!=son[rt].end();++it)sum-=val[stk[++top]=it->se];son[rt].clear();while(top){for(It it=son[stk[top]].begin();it!=son[stk[top]].end();++it)son[rt][it->fi]=merge(son[rt][it->fi],it->se);--top;}
}
int main(){n=read(),m=read();for(ri i=1,up=n*m;i<=up;++i)a[i]=read();for(ri l=1,r=m,i=1;i<=n;++i,l+=m,r+=m)build(i,l,r);for(ri i=1;i<=tot;++i)sum+=val[i];ans=sum;for(ri i=2;i<=m;++i)update(),ans+=sum;cout<<ans;return 0;
}

sequence

签到题（然而签到失败）
考虑离线处理，然后从右向左枚举左端点，看有哪些右端点满足条件。
每个位置作为起点向右只有 l o g log log种不同的结果，我们用链表维护一下这些结果然后用 b i t bit bit统计贡献即可。
代码：

#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){static char buf[rlen],*ib,*ob;(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));return ib==ob?-1:*ib++;
}
inline int read(){int ans=0;char ch=gc();while(!isdigit(ch))ch=gc();while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();return ans;
}
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e5+5,M=5e5+5;
int n,m,k,a[N],suf[N];
ll ans[M];
vector<pii>qry[M];
namespace Bit{ll s1[N],s2[N];inline int lowbit(const int&x){return x&-x;}inline void update(const int&x,const int&v){for(ri i=x;i<=n;i+=lowbit(i))s1[i]+=(ll)x*v,s2[i]+=v;}inline ll query(const int&x){ll ret=0;for(ri i=x;i;i^=lowbit(i))ret+=(ll)(x+1)*s2[i]-s1[i];return ret;}inline void update(int l,int r,int v){update(l,v),update(r+1,-v);}
}
int main(){n=read(),m=read(),k=read();for(ri i=1;i<=n;++i)a[i]=read();for(ri i=1,x;i<=m;++i)x=read(),qry[x].push_back(pii(read(),i));for(ri val,last,i=n;i;--i){val=a[i],suf[i]=i+1,last=i;for(ri pre=i,p=i+1;p<=n;pre=p,p=suf[p]){if((val&a[p])^val){if(val==val/k*k)Bit::update(last,p-1,1);val&=a[p],last=p;}else suf[pre]=suf[p];}if(val==val/k*k)Bit::update(last,n,1);for(ri j=0;j<qry[i].size();++j)ans[qry[i][j].se]=Bit::query(qry[i][j].fi);}for(ri i=1;i<=m;++i)cout<<ans[i]<<'\n';return 0;
}

permutation

一道简单的推式子题，原题是codeforces906G，但不知道为什么毒瘤出题人要卡 O ( n l o g n 2 ) O(nlog^2_n) O(nlogn2​)的分治 n t t ntt ntt，行吧那么我们就用 O ( n l o g n ) O(nlog_n) O(nlogn​)的倍增。
其实先考虑暴力 d p dp dp，枚举最大值放哪里，然后发现需要把剩下 n − 1 n-1 n−1个数放进 a + b − 2 a+b-2 a+b−2个黑白环再钦定其中 a − 1 a-1 a−1个为黑环剩余为白环，因此 a n s = s 1 n − 1 a + b − 2 C a + b − 2 a − 1 ans=s1_{n-1}^{a+b-2}C_{a+b-2}^{a-1} ans=s1n−1a+b−2​Ca+b−2a−1​
倍增处理方法和代码看这里

本文链接：https://my.lmcjl.com/post/19990.html