Description

Input

Output

Sample Input

3 4
1 2 3
1 0 0
1 0 0
2 1
0 1
2 2
2 1

Sample Output

3
6
2

Data Constraint

Solution

• 一開始看錯題了，以為直接修改就可以了，結果爆零……

• 這題顯然LCT可以做，要多暴力有多暴力。

• 但我們用些巧法，發掘一下性質。

• 這左旋右旋就相當于Splay的操作，而操作前后中序遍歷不變！

• 而一個點子樹對應的區間在中序遍歷中是連續的一段。

• 于是我們就可以根據中序遍歷開一顆線段樹，維護區間乘積。

• 而旋轉操作實際上只會改變兩個點的子樹區間，分類討論并單點修改即可。

• 時間復雜度 O(N?log?N) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=2e5+5,mo=1e9+7; int tot,qx,qy,top; long long qz; int id[N],fa[N],size[N],s[N][2],pre[N],key[N],begin[N],st[N]; long long a[N],sum[N],mul[N<<2]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline void update(int x) {size[x]=size[s[x][0]]+size[s[x][1]]+1;sum[x]=(a[begin[x]+size[x]-1]-a[begin[x]-1]+mo)%mo; } void dfs(int x) {begin[x]=tot+1;if(s[x][0]) dfs(s[x][0]);id[x]=++tot;pre[id[x]]=x;if(s[x][1]) dfs(s[x][1]);size[x]=size[s[x][0]]+size[s[x][1]]+1; } void bfs(int rt) {while(top || rt){while(rt){begin[rt]=tot+1;st[++top]=rt;rt=s[rt][0];}rt=st[top--];id[rt]=++tot;pre[id[rt]]=rt;rt=s[rt][1];}int l=0,r=1;st[1]=1;while(l<r){int x=st[++l];if(s[x][0]) st[++r]=s[x][0];if(s[x][1]) st[++r]=s[x][1];}for(int i=r;i;i--) size[i]=size[s[i][0]]+size[s[i][1]]+1; } void make(int v,int l,int r) {if(l==r){mul[v]=sum[pre[l]]%mo;return;}int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);mul[v]=mul[v<<1]*mul[v<<1|1]%mo; } void change(int v,int l,int r) {if(l==r){mul[v]=qz;return;}int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid); else change(v<<1|1,mid+1,r);mul[v]=mul[v<<1]*mul[v<<1|1]%mo; } long long find(int v,int l,int r) {if(qx<=l && r<=qy) return mul[v];int mid=l+r>>1;long long ss=1;if(qx<=mid) ss=find(v<<1,l,mid);if(qy>mid) ss=ss*find(v<<1|1,mid+1,r)%mo;return ss; } inline bool pd(int x) {return s[fa[x]][1]==x; } int main() {freopen("splay.in","r",stdin);freopen("splay.out","w",stdout);int n=read(),q=read();for(int i=1;i<=n;i++){key[i]=read();int x=read(),y=read();if(x) fa[s[i][0]=x]=i;if(y) fa[s[i][1]=y]=i;}dfs(1);for(int i=1;i<=n;i++) a[i]=(a[i-1]+key[pre[i]])%mo;for(int i=1;i<=n;i++) sum[i]=(a[begin[i]+size[i]-1]-a[begin[i]-1]+mo)%mo;make(1,1,n);while(q--){int opt=read(),x=read();if(opt==2){qx=begin[x],qy=begin[x]+size[x]-1;printf("%lld\n",(find(1,1,n)+mo)%mo);}elseif(opt==1){int y=s[x][1];if(!y) continue;if(fa[y]=fa[x]) s[fa[x]][pd(x)]=y;fa[y]=fa[x];if(s[x][1]=s[y][0]) fa[s[y][0]]=x;fa[s[y][0]=x]=y;begin[y]=begin[x];update(x);update(y);qx=id[x],qz=sum[x];change(1,1,n);qx=id[y],qz=sum[y];change(1,1,n);}else{int y=s[x][0];if(!y) continue;if(fa[y]=fa[x]) s[fa[x]][pd(x)]=y;if(s[x][0]=s[y][1]) fa[s[y][1]]=x;fa[s[y][1]=x]=y;begin[x]=id[y]+1;update(x);update(y);qx=id[x],qz=sum[x];change(1,1,n);qx=id[y],qz=sum[y];change(1,1,n);}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5662. 【GDOI2018Day1模拟4.17】尺树寸泓的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。