T1
多测不清空，爆零两行泪。
考场想法过于sb，树上带修莫队+查询区间 \(\min/\max\) ，然后就不会了。
结果写的暴力多测没清空，爆零了....改了之后竟然能切？
判断排列直接写个hash就行了...
T2
考场以为是可追溯化并查集之前颓游记的时候发现的，然而并不会，想了想，发现可以用个栈存下操作，然后就不知道该怎么处理了，打了60pts就跑路了。
竟然是套路题
有个东西叫线段树分治，就是维护每个操作能产生影响的区间，统计答案dfs一遍，回溯时撤销当前操作影响。
把每一个操作插入到其能产生影响的区间中，然后用个可撤销并查集维护 \(size\) 大小。
可撤销并查集，就是用个栈存下操作，不能用路径压缩，不然会出错，要用启发式合并来保证复杂度。
Code
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using std::sort;
using std::pair;
using std::vector;
using std::upper_bound;
#define fi first
#define se second
using std::make_pair;
#define pack make_pair
#define push emplace_back
typedef pair<int,int> my;
#define re register
const int MAX = 1e5+3;
const int mod = 1e9+7;
#define long long long
#define scanf oma=scanf
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,m;
long inv[MAX],ans=1;
struct data
{ int op,u,v; }q[MAX];
vector<pair<my,int>>s;
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Data_Structures
{
auto swap = [](int &a,int &b) { int t=a; a=b,b=t; };
struct DSU
{
int top;
my sta[MAX];
int fa[MAX],size[MAX];
void init()
{ for(re int i=1; i<=n; i++) { size[fa[i] = i] = 1; } }
int find(int x)
{ return x!=fa[x]?find(fa[x]):fa[x]; }
void merge(int x,int y)
{
x = find(x),y = find(y);
if(x!=y)
{
if(size[x]<size[y])
{ swap(x,y); }
fa[y] = x,ans = ans*inv[size[x]]%mod*inv[size[y]]%mod*(size[x] += size[y])%mod;
}
sta[++top] = pack(x,y);
}
void revoke(int cnt)
{
int x,y; my now;
//debug("<---->");
while(cnt)
{
cnt--;
now = sta[top--],x = now.fi,y = now.se;
if(x==y)
{ continue ; }
//printf("x=%d y=%d sizex=%d sizey=%d\n",x,y ,size[x],size[y]);
ans = ans*inv[size[x]]%mod*(size[x] -= size[y])%mod*size[fa[y] = y]%mod;
}
//debug(">----<");
}
}ds;
struct Segment_Tree
{
vector<my>val[MAX<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mid (l+r>>1)
void insert(int p,int l,int r,int lp,int rp,my w)
{
if(lp<=l&&r<=rp)
{ val[p].push(w); return ; }
if(lp<=mid)
{ insert(ls(p),l,mid,lp,rp,w); }
if(rp>mid)
{ insert(rs(p),mid+1,r,lp,rp,w); }
}
void dfs(int p,int l,int r)
{
for(auto x : val[p])
{ ds.merge(x.fi,x.se); }
if(l==r)
{ printf("%lld\n",ans); goto jump; }
dfs(ls(p),l,mid),dfs(rs(p),mid+1,r);
jump: ;
/*printf("l=%d r=%d\n",l,r);*/ ds.revoke(val[p].size());
}
}Tree;
}using namespace Data_Structures;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
freopen("b.in","r",stdin); freopen("b.out","w",stdout);
cin >> n >> m; inv[1] = 1;
for(re int i=1; i<=m; i++)
{
cin >> q[i].op >> q[i].u >> q[i].v;
if(q[i].u>q[i].v)
{ swap(q[i].u,q[i].v); }
if(q[i].op==2)
{ s.push(pack(pack(q[i].u,q[i].v),i)); }
}
sort(s.begin(),s.end());
for(re int i=1; i<=m; i++)
{
if(q[i].op==1)
{
int r;
int pos = upper_bound(s.begin(),s.end(),pack(pack(q[i].u,q[i].v),i))-s.begin();
if(pos==s.size())
{ Tree.insert(1,1,m,i,m,pack(q[i].u,q[i].v)); continue ; }
pair<my,int> p = s[pos];
if(p.fi!=pack(q[i].u,q[i].v))
{ Tree.insert(1,1,m,i,m,pack(q[i].u,q[i].v)); /*r = m;*/ }
else
{ Tree.insert(1,1,m,i,p.se-1,pack(q[i].u,q[i].v)); /*r = p.se-1; printf("%d %d\n",i,p.se);*/ }
//printf("l=%d r=%d\n",i,r);
}
}
for(re int i=2; i<=n; i++)
{ inv[i] = (mod-mod/i)*inv[mod%i]%mod; }
ds.init(); Tree.dfs(1,1,m);
return 0;
};
};
signed main()
{ return OMA::main(); }
T3
考场啥也不会，cdq也没写出来...
先考虑一个这样一个问题，给定三个排列 \(a,b,c\) ，求满足 \(a_{i}<a_{j},b_{i}<b_{j},c_{i}<c_{j}\) 的 \((i,j)\) 个数，其中 \(a\) 序列为下标序列，直接写cdq肯定不行。
用题解做法 对 \((a,b),(a,c),(b,c)\) 这三对分别求一遍二维偏序，那么每一对 \((i,j)\) 不是满足二维偏序，就是满足三维偏序，因为 \(a\) 序列为下标，肯定满足 \(i<j\) ， \(b_{i},b_{j}\) 之间的关系只有大于小于， \(c_{i},c_{j}\) 同理，俩都大于交换一下就行。
那么这样在统计给这三对二维偏序求和时，如果 \((i,j)\) 满足的是三维偏序关系，会被算三遍，否则只会算一遍。
设二维偏序之和为 \(m\) ， 所以三维偏序的数量就是 \(\frac{m-\tbinom{n}{2}}{2}\) 。
这是没有-1的情况，有-1的情况，则预处理出从 \(q\) 没有的数中选，比 \(i\) 大的概率，用树状数组维护的时候插概率就行了，如果都是-1，那么概率就是 \(\frac{1}{2}\) 。因为贡献是1，所以期望就是概率。
不过战神的容斥做法更好搞一些，也更好理解。
Code
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using std::sort;
using std::vector;
#define re register
#define pack push_back
const int MAX = 1e6+3;
#define long long long
#define scanf oma=scanf
const int mod = 998244353;
const int inv2 = 499122177;
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
long res;
long rec[MAX];
bool tub[MAX];
int seq[MAX],tot;
int n,p[MAX],q[MAX];
auto quickpow = [](int a,int b,int res = 1)
{
while(b)
{
if(b&1)
{ res = 1ll*res*a%mod; }
a = 1ll*a*a%mod,b >>= 1;
}
return res;
};
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Data_Structures
{
struct BIT
{
int val[MAX];
#define lowbit(x) x&-x
void clear()
{ memset(val,0,sizeof(int)*(n+1)); }
void modify(int x,int w)
{ for(re int i=x; i<=n; i+=lowbit(i)) { (val[i] += w) %= mod; } }
int query(int x,int res = 0)
{ for(re int i=x; i; i-=lowbit(i)) { (res += val[i]) %= mod; } return res; }
}Tree;
}using namespace Data_Structures;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
freopen("c.in","r",stdin); freopen("c.out","w",stdout);
cin >> n;
for(re int i=1; i<=n; i++)
{ cin >> p[i]; }
for(re int i=1; i<=n; i++)
{ cin >> q[i]; if(q[i]!=-1) { seq[++tot] = i; tub[q[i]] = true; } }
for(re int i=1; i<=tot; i++)
{ (res += Tree.query(p[seq[i]])) %= mod; Tree.modify(p[seq[i]],1); }
Tree.clear();
for(re int i=1; i<=tot; i++)
{ (res += Tree.query(q[seq[i]])) %= mod; Tree.modify(q[seq[i]],1); }
Tree.clear(); sort(seq+1,seq+1+tot,[](const int &x,const int &y) { return q[x]<q[y]; });
for(re int i=1; i<=tot; i++)
{ (res += Tree.query(p[seq[i]])) %= mod; Tree.modify(p[seq[i]],1); }
//printf("res=%lld\n",res);
res = (res-1ll*tot*(tot-1)%mod*inv2%mod+mod)%mod*inv2%mod,tot = 0;
//printf("res=%lld\n",res);
for(re int i=1; i<=n; i++)
{
if(!tub[i])
{ seq[++tot] = i; /*printf("i=%d ",i);*/ }
}
//printf("\ntot=%d\n",tot);
long inv = quickpow(tot,mod-2);
for(re int i=1,pos=1; i<=n; i++)
{
while(pos<=tot&&seq[pos]<=i)
{ pos++; }
//printf("%d\n",pos);
rec[i] = (tot-pos+1)*inv%mod;
//printf("rec[%d]=%lld\n",i,rec[i]);
}
Tree.clear();
for(re int i=1; i<=n; i++)
{
if(q[i]!=-1)
{ Tree.modify(p[i],rec[q[i]]); }
else
{ (res += Tree.query(p[i])) %= mod; }
}
Tree.clear();
for(re int i=n; i; i--)
{
if(q[i]!=-1)
{ Tree.modify(p[i],mod+1-rec[q[i]]); }
else
{ (res += Tree.query(n)-Tree.query(p[i])+mod) %= mod; }
}
Tree.clear();
for(re int i=1; i<=n; i++)
{ if(q[i]==-1) { (res += Tree.query(p[i])) %= mod; Tree.modify(p[i],inv2); } }
printf("%lld\n",res);
return 0;
};
};
signed main()
{ return OMA::main(); }
T4
不会，咕...