Noip模拟96 2021.11.12

#include
#define int long long
using namespace std;
namespace AE86{
	FILE *wsn;
	#define gc() p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++
	char buf[1<<20],*p1=buf,*p2=buf;
	auto read=[](){
		int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
	};
	auto write=[](int x,char opt='\n'){
		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
		for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
	};
}using namespace AE86;

const int NN=1e5+5,mod=1e9+7;
typedef pair PII;
#define fi first
#define se second
#define mp make_pair
int n,m,inv[NN],ans=1;
struct node{int x,y;}e[NN];
namespace DSU{
	int fa[NN],siz[NN],top;
	struct Stack{int x,y,szx,szy,tot;}stk[NN];
	inline int getfa(int x){return (fa[x]==x)?x:getfa(fa[x]);}
	inline void merge(int x,int y){
		x=getfa(x); y=getfa(y);
		if(x==y) return;
		if(siz[x]>siz[y]) swap(x,y);
		stk[++top]=(Stack){x,y,siz[x],siz[y],siz[x]+siz[y]};
		ans=ans*inv[siz[x]]%mod*inv[siz[y]]%mod;
		ans=ans*(siz[x]+siz[y])%mod;
		fa[x]=y; siz[y]+=siz[x];
	}
	inline void back(int lst){
		while(top>lst){
			Stack now=stk[top--];
			ans=ans*inv[now.tot]%mod;
			ans=ans*now.szx%mod*now.szy%mod;
			fa[now.x]=now.x; siz[now.y]-=now.szx;
		}
	}
}using namespace DSU;
struct SNOWtree{
	#define lid (id<<1)
	#define rid (id<<1|1)
	#define mid ((l+r)>>1)
	vector tag[NN<<2];
	inline void insert(int id,int l,int r,int L,int R,int v){
		if(l>R||rhas;
struct update{int l,r,i;};vector upd;
namespace WSN{
	inline short main(){
		wsn=freopen("b.in","r",stdin);
		wsn=freopen("b.out","w",stdout);
		n=read();m=read(); inv[0]=inv[1]=1;
		for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
		for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		for(int i=1;i<=m;i++){
			int opt=read(); e[i].x=read(),e[i].y=read();
			if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
			if(opt&1) has[mp(e[i].x,e[i].y)]=i;
			else{
				upd.push_back(update{has[mp(e[i].x,e[i].y)],i-1,has[mp(e[i].x,e[i].y)]});
				has.erase(has.find(mp(e[i].x,e[i].y)));
			}
		}
		for(auto x:has)upd.push_back(update{x.se,m,x.se});
		for(auto x:upd)tr.insert(1,1,m,x.l,x.r,x.i);
		tr.dfs(1,1,m);
		return 0;
	}
}
signed main(){return WSN::main();}

#include
#define int long long
using namespace std;
namespace AE86{
	FILE *wsn;
	#define gc() p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++
	char buf[1<<20],*p1=buf,*p2=buf;
	auto read=[](){
		int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
	};
	auto write=[](int x,char opt='\n'){
		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
		for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
	};
}using namespace AE86;
const int NN=1e6+5,mod=998244353;
inline int qmo(int a,int b,int ans=1){for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
int n,a[NN],b[NN],c[NN],tmp,v2;
int M,tt,ans,no[NN],cnt,P[NN][2];
bool vis[NN];
struct BIT{
	int c[NN];
	inline void update(int x,int v){while(x0){
			big+=P[p[i].y][1];
			ans+=tr.query(p[i].y-1)+P[p[i].y][0]*tmp%mod; ans%=mod;
			tr.update(p[i].y,1);
		}else{
			ans+=big+tmp*v2%mod; ans%=mod;
			++tmp;
		}
	}
	return ans;
}
namespace WSN{
	inline short main(){
		wsn=freopen("c.in","r",stdin);
		wsn=freopen("c.out","w",stdout);
		n=read(); v2=qmo(2,mod-2);
		for(int i=1;i<=n;++i)b[i]=read(),a[i]=i;
		for(int i=1;i<=n;++i){
			c[i]=read();
			if(c[i]>0)vis[c[i]]=1;
		}for(int i=1;i<=n;++i)if(!vis[i])no[++cnt]=i;
		tmp=qmo(cnt,mod-2);
		for(int i=1;i<=n;++i){
			P[i][0]=(lower_bound(no+1,no+cnt+1,i)-no-1)*tmp%mod;
			P[i][1]=(cnt-(upper_bound(no+1,no+cnt+1,i)-no)+1)*tmp%mod;
		}
		int tmp1=calc(a,b),tmp2=calc(a,c),tmp3=calc(b,c);
		M=tmp1+tmp2+tmp3;
		tt=n*(n-1)%mod*v2%mod;
		ans=(M-tt+mod)%mod*v2%mod;
		write(ans);
		return 0;
	}
}
signed main(){return WSN::main();}