1.[TJOI2018]数学计算
傻逼题
会发现符合线段树分治的特点
每个数的操作范围都是连续的
然后就等于区间修改了
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long #define me(x) memset(x,0,sizeof(x)) #define mid ((h+t)>>1) namespace IO {char ss[1<<24],*A=ss,*B=ss;IL char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;}template<class T>void read(T &x){rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;}char sr[1<<24],z[20]; int Z,C=-1;template<class T>void wer(T x){if (x<0) sr[++C]='-',x=-x;while (z[++Z]=x%10+48,x/=10);while (sr[++C]=z[Z],--Z);}IL void wer1(){sr[++C]=' ';}IL void wer2(){sr[++C]='\n';}template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}template<class T>IL T MAX(T x,T y){return x>y?x:y;}template<class T>IL T MIN(T x,T y){return x<y?x:y;} }; using namespace IO; int n,mo; const int N=2e5; int s[N],t[N]; struct sgt{ll lazy[N*4];void clear(){rep(i,0,N*4-1) lazy[i]=1;}void change(int x,int h,int t,int h1,int t1,int k){if (h1<=h&&t<=t1){(lazy[x]*=k)%=mo; return;}if (h1<=mid) change(x*2,h,mid,h1,t1,k);if (mid<t1) change(x*2+1,mid+1,t,h1,t1,k);}ll query(int x,int h,int t,int pos,ll k){(k*=lazy[x])%=mo;if (h==t) return k;if (pos<=mid) return query(x*2,h,mid,pos,k);else return query(x*2+1,mid+1,t,pos,k);} }S; int main() {int T;read(T);rep(tt,1,T){read(n); read(mo); me(s); me(t);int kk,x;rep(i,1,n){read(kk); read(x);if (kk==1){s[i]=x; t[i]=n;} else t[x]=i-1;}S.clear();rep(i,1,n)if (t[i])S.change(1,1,n,i,t[i],s[i]);rep(i,1,n) wer(S.query(1,1,n,i,1ll)),wer2();}fwrite(sr,1,C+1,stdout);return 0; }
2.[TJOI2018]智力竞赛
出题人语文水平真没话说
就是求dag最小可相交路径覆盖（网上还有人说有向图那这根本做不了）
比较显然的是如果我们确定了要取哪些点就变成了上述问题
按照网络流的一般套路应该是逐渐增大然后逐渐流量增大的
但是路径覆盖等于n-最大流 所以流量是在不断变小的
于是我们只能选择二分答案了
另外可相交路径覆盖
需要先求个传递闭包，然后再连边
如果不想交路径覆盖 就直接连边
连边方法就是将点拆成入点和出点 从一个的出点往另一个的入点连边
由于floyd没有用bitset写。。。 权值没有离散化。。。
常数挺大的。。反正这种题能过就行了。。。
代码：
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long #define me(x) memset(x,0,sizeof(x)) #define mid ((h+t)>>1) namespace IO {char ss[1<<24],*A=ss,*B=ss;IL char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;}template<class T>void read(T &x){rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;}char sr[1<<24],z[20]; int Z,C=-1;template<class T>void wer(T x){if (x<0) sr[++C]='-',x=-x;while (z[++Z]=x%10+48,x/=10);while (sr[++C]=z[Z],--Z);}IL void wer1(){sr[++C]=' ';}IL void wer2(){sr[++C]='\n';}template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}template<class T>IL T MAX(T x,T y){return x>y?x:y;}template<class T>IL T MIN(T x,T y){return x<y?x:y;} }; using namespace IO; int n,mo; const int N=2e5; int s[N],t[N]; struct sgt{ll lazy[N*4];void clear(){rep(i,0,N*4-1) lazy[i]=1;}void change(int x,int h,int t,int h1,int t1,int k){if (h1<=h&&t<=t1){(lazy[x]*=k)%=mo; return;}if (h1<=mid) change(x*2,h,mid,h1,t1,k);if (mid<t1) change(x*2+1,mid+1,t,h1,t1,k);}ll query(int x,int h,int t,int pos,ll k){(k*=lazy[x])%=mo;if (h==t) return k;if (pos<=mid) return query(x*2,h,mid,pos,k);else return query(x*2+1,mid+1,t,pos,k);} }S; int main() {int T;read(T);rep(tt,1,T){read(n); read(mo); me(s); me(t);int kk,x;rep(i,1,n){read(kk); read(x);if (kk==1){s[i]=x; t[i]=n;} else t[x]=i-1;}S.clear();rep(i,1,n)if (t[i])S.change(1,1,n,i,t[i],s[i]);rep(i,1,n) wer(S.query(1,1,n,i,1ll)),wer2();}fwrite(sr,1,C+1,stdout);return 0; }
3.
好像老早写过了就不看了
4.[TJOI2018]异或
我觉得我有点傻逼。。。
首先这题显然是0/1trie去匹配
然后关键在于怎么实现子树和链操作
于是我很自然的想到了树链剖分+线段树（每个节点上一课trie）
于是成功达到了时间$nlog^3{n}$ 空间$nlog^2{n}$的傻逼境界
不过开O2还3s再加上树剖的常数小我觉得是跑的过得？？
但是空间就gg了啊 我们得记录ls，rs n*30*20*2这个没法艹过去
虽然trie的空间可能到不了n*30但感觉上还是过不去所以就不写了
另外如果空间只超过一点的话我记得有个技巧是把ls，rs压成一个unsigned int+一个unsigned short int
然后合成一个ll 再分成两个23位
所以还是看正解吧。。
因为是trie树 所以支持差分
那么建立可持久化0/1trie然后差分做就可以了
对于子树是按照dfn建立可持久，链是按照父亲建立
代码：
