HDU多校2

HDU多校2

赛中五题，总结：签到、签到、枚举、枚举以及一道讨论到头大的线段树

1002

题意：去掉字符串中的“std::make_tuple”。

思路：遇到's'直接i+=14即可。遍历输出。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],a[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
    scanf("%s",s+1);
    n=strlen(s+1);m=0;
    L(i,1,n){
        if(s[i]=='s')i+=14;
        else a[++m]=s[i];
    }
    L(i,1,m)printf("%c",a[i]);printf("\n");

}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1012

题意：三种硬币价值分别为7、31、365，求凑出n元需要的硬币最小数量，或者不能凑出n。

思路：因为是数量最小，所以很明显的，7的数量不能超过31个，31的数量不能超过365个。直接枚举7的数量和31的数量，求解365的数量，然后求数量和最小值即可，复杂度O(31*365*t)，约为1e7。（当然可以用贪心，但是有点小复杂）

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],a[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
    scanf("%lld",&n);
    ans=inf;
    L(i,0,30)L(j,0,364){
        m=n-i*7-j*31;
        if(m%365==0&&m>=0)ans=min(ans,i+j+m/365);
    }
    if(ans==inf)printf("-1\n");
    else printf("%lld\n",ans);

}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1009

题意：数学题，已知：

  1. P×Q≡1mod  MP \times Q \equiv 1 \mod M
  2. e=r×Pmod  Me = r \times P \mod M
  3. r=e×Qmod  Mr = e \times Q \mod M

已知 P,Q,e，求 r。

思路：k∗M=P∗Q−1k*M = P*Q-1，且M是质数。因此枚举 (P*Q-1) 的质因数表示M，然后通过式3计算r，并通过式2验算即可。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

bool visprime[N];
ll prime[N];
void oulasai(ll n){
    cnt=0;
    L(i,2,n){
        if(!visprime[i])prime[++cnt]=i;
        L(j,1,cnt){
            if(i*prime[j]>n) break;
            visprime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void solve(){
    ll e,r,p,q,m;
    scanf("%lld%lld%lld",&p,&q,&e);
    n=0;
    k=p*q-1;mx=max(e,max(p,q));
    L(i,1,cnt){
        if(prime[i]*prime[i]>k)break;
        if(k%prime[i]==0){
            if(prime[i]>mx)a[++n]=prime[i];
            while(k%prime[i]==0)k/=prime[i];
        }
    }
    if(k>1)a[++n]=k;
    L(i,1,n){
        m=a[i];
        r=e*q%m;
        if(r*p%m==e){
            printf("%lld\n",r);
            return;
        }
    }
    printf("shuanQ\n");

}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    oulasai(2000000);
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1007

题意：阅读理解题。给定n个区间，问区间重叠前有几个区间。

（题面太长让队友去开了） 思路：按区间左端点排序，直到有一个区间和后一个区间重叠为止，看前面的区间数量。

1011

题意：给定长为n的数组a，m次询问。每次询问一个区间，求从区间内任选四个数后，分成两对，求两对的平方差（左减右）之和的最大值。

思路：(ai−aj)(ai+aj)=ai2−aj2(a_i-a_j)(a_i+a_j)=a_i^2-a_j^2 ，因此我们先将所有ai平方。那么问题就转换为了从区间内从左往右选四个数 a,b,c,d，求 max( a-b+c-d , a+b-c-d )。建立线段树，分类讨论左区间与右区间合并时，各状态的最大值即可，具体转译过程可以看代码。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=16,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r;vector<ll>w;}trs[N*4];
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

/*
1:-
2:+
3:--
4:-+
5:+-
6:++
7:--+
8:-+-
9:+--
10:-++
11:+-+
12:++-
13:++--
14:+-+-
*/

vector<ll>co(vector<ll>x,vector<ll>y){
    vector<ll>res(16);
    res[1]=max(x[1],y[1]);
    res[2]=max(x[2],y[2]);

    res[3]=max(x[3],max(x[1]+y[1],y[3]));
    res[4]=max(x[4],max(x[1]+y[2],y[4]));
    res[5]=max(x[5],max(x[2]+y[1],y[5]));
    res[6]=max(x[6],max(x[2]+y[2],y[6]));

    res[7]=max(x[7],max(x[3]+y[2],max(x[1]+y[4],y[7])));
    res[8]=max(x[8],max(x[4]+y[1],max(x[1]+y[5],y[8])));
    res[9]=max(x[9],max(x[5]+y[1],max(x[2]+y[3],y[9])));
    
    res[10]=max(x[10],max(x[4]+y[2],max(x[1]+y[6],y[10])));
    res[11]=max(x[11],max(x[5]+y[2],max(x[2]+y[4],y[11])));
    res[12]=max(x[12],max(x[6]+y[1],max(x[2]+y[5],y[12])));

    res[13]=max(x[13],max(x[12]+y[1],max(x[6]+y[3],max(x[2]+y[9],y[13]))));
    res[14]=max(x[14],max(x[11]+y[1],max(x[5]+y[5],max(x[2]+y[8],y[14]))));
    return res;
}

void push_up(ll k){
    ll l=k*2,r=k*2+1;
    trs[k].w=co(trs[l].w,trs[r].w);
}

void bd_tree(ll k,ll l,ll r){
    trs[k].l=l,trs[k].r=r;
    if(l==r){
        trs[k].w.clear();
        trs[k].w.pb(-inf);
        trs[k].w.pb(-a[l]);
        trs[k].w.pb(a[l]);
        L(i,3,14)trs[k].w.pb(-inf);
        return;
    }
    ll mid=(l+r)/2;
    bd_tree(k*2,l,mid);
    bd_tree(k*2+1,mid+1,r);
    push_up(k);
}

vector<ll> query(ll k,ll pl,ll pr){
    if(trs[k].l>=pl&&trs[k].r<=pr){
        return trs[k].w;
    }
    ll mid=(trs[k].l+trs[k].r)/2;
    if(mid>=pl&&mid+1<=pr){
        return co(query(k*2,pl,pr),query(k*2+1,pl,pr));
    }
    else if(mid>=pl)return query(k*2,pl,pr);
    else return query(k*2+1,pl,pr);
}

void solve(){
    scanf("%lld%lld",&n,&m);
    L(i,1,n){
        scanf("%lld",&a[i]);
        a[i]*=a[i];
    }
    bd_tree(1,1,n);
    while(m--){
        scanf("%lld%lld",&l,&r);
        vector<ll>res=query(1,l,r);
        ans=max(res[13],res[14]);
        printf("%lld\n",ans);
    }
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}

1003

题意：给定长为n的数组a，q次操作，有两种操作：

  1. 选择一个区间，然后复制该区间插入到该区间尾部；
  2. 询问从左往右数第x个数的值。

（题目特别标注操作1的总次数不会超过20000，让我不禁去往bitset上去想，直到最后二十分钟才想通从后往前做的真谛，结果来不及） 思路：因为不论该数组如何复制变长，询问的x依旧不超过原数组长n。因此我们可以将询问都记录下来，从后往前遍历，举个栗子：当前操作1的区间为 [l,r]，那么在此操作1后面的询问第x个数，如果x>r，那么它就相当于询问此操作1之前的第x-(r-l+1)；如果x<=r，那么该询问就不受此操作1的影响。由于最后输出的是所有询问的异或和，那么一个数被多次询问的话，我们只需将询问次数 mod 2 即可。 考虑bitset，令bi[i]表示当前第i个数是否被询问，对于每个操作1，将区间[r+1,n]右移(r-l+1)位，与区间[1,r]异或即可。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e5+10,M=16,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll k,x,y;}q[N];
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
bitset<N>bi,ba,bb,bs;

void solve(){
    scanf("%lld%lld",&n,&m);
    L(i,1,n)scanf("%lld",&a[i]);
    bi.reset();ans=0;
    L(i,1,m){
        scanf("%lld",&k);
        if(k==1){
            scanf("%lld%lld",&x,&y);
            q[i]={k,x,y};
        }
        else{
            scanf("%lld",&x);
            q[i]={k,x};
        }
    }
    R(i,m,1){
        if(q[i].k==1){
            l=q[i].x,r=q[i].y;
            ba=bi&(bs>>(N-r-1));
            bb=bi&(bs<<(r+1));
            bi=ba^(bb>>(r-l+1));
        }
        else{
            bi.flip(q[i].x);
        }
        //cout<<bi<<endl;
    }
    L(i,1,n){
        if(bi[i]){
            ans^=a[i];//printf("%lld ",i);
        }
    }
    printf("%lld\n",ans);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    bs=~bs;
    scanf("%lld",&t);
    while(t--)solve();
}

1001

题意：n个点，n-1条有向边，且所有点都可以到达点1。每次询问给出三个集合A,B,C，从A,B,C中分别选一个城市后，Alice从A中的城市出发到C中的城市，Bob从B中的城市到C中的城市，求有多少个城市Alice和Bob都会经过。

（题目读假了，没注意到有向边） 思路：很明显的树链剖分，以点1为根建树。因为是A->C,B->C，所以C一定是A,B的祖先。对于A中的每一个点a，标记树链1到a；对于B中的每一个点b，标记树链1到b；对于C中的每一个点c，标记以c为根的子树。最后查询只需询问有多少个点被abc都标记过了，线段树区间标记即可。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,nz,ansx,ansy,lim,num,sum,pos,tot,root,block,key=1e9,cnt,mn,mx,ans;
ll a[N],head[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,sum[3];bool del,tag[3];}trs[N*4];
struct tree{ll fa,dep,dfn,siz,son,top,w;}tr[N];
struct edge{ll to,nxt;}eg[N*2];

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void add(ll u,ll v){
    eg[++cnt].to=v;
    eg[cnt].nxt=head[u];
    head[u]=cnt;
}

void push_up(ll k){
    L(i,0,2){
        trs[k].sum[i]=trs[k*2].sum[i]+trs[k*2+1].sum[i];
    }
}

void push_down(ll k){
    ll l=k*2,r=k*2+1;
    if(trs[k].del){
        trs[l].del=1;trs[r].del=1;
        L(i,0,2){
            trs[l].sum[i]=0,trs[r].sum[i]=0;
            trs[l].tag[i]=0,trs[r].tag[i]=0;
        }
        trs[k].del=0; 
    }
    L(i,0,2){
        trs[l].tag[i]|=trs[k].tag[i],trs[r].tag[i]|=trs[k].tag[i];
        if(trs[k].tag[i]){
            if(i==0)trs[l].sum[i]=trs[l].r-trs[l].l+1;
            else trs[l].sum[i]=trs[l].sum[i-1];
            if(i==0)trs[r].sum[i]=trs[r].r-trs[r].l+1;
            else trs[r].sum[i]=trs[r].sum[i-1];
        }
        trs[k].tag[i]=0;
    }
}

void bd_tree(ll k,ll l,ll r){
    trs[k].del=0;
    L(i,0,2)trs[k].tag[i]=0;
    trs[k].l=l,trs[k].r=r;
    if(l==r){
        L(i,0,2)trs[k].sum[i]=0;
        return;
    }
    ll mid=(l+r)/2;
    bd_tree(k*2,l,mid);
    bd_tree(k*2+1,mid+1,r);
    push_up(k);
}

ll query(ll k,ll pl,ll pr){
    ll ml=0,mr=0;
    if(trs[k].l>=pl&&trs[k].r<=pr){
        return trs[k].sum[2];
    }
    push_down(k);
    ll mid=(trs[k].l+trs[k].r)/2;
    if(mid>=pl)ml=query(k*2,pl,pr);
    if(mid+1<=pr)mr=query(k*2+1,pl,pr);
    return ml+mr;
}

void modify(ll k,ll pl,ll pr,ll p){
    if(trs[k].l>=pl&&trs[k].r<=pr){
        trs[k].tag[p]=1;
        if(p==0)trs[k].sum[p]=trs[k].r-trs[k].l+1;
        else trs[k].sum[p]=trs[k].sum[p-1];
        return;
    }
    push_down(k);
    ll mid=(trs[k].l+trs[k].r)/2;
    if(mid>=pl)modify(k*2,pl,pr,p);
    if(mid+1<=pr)modify(k*2+1,pl,pr,p);
    push_up(k);
}

void del(){
    L(i,0,2){
        trs[1].sum[i]=0;
        trs[1].tag[i]=0;
    }
    trs[1].del=1;
}

void dfs1(ll x,ll ac){
    tr[x].fa=ac;
    tr[x].dep=tr[tr[x].fa].dep+1;
    tr[x].siz=1;
    ll k=head[x];
    while(k){
        ll y=eg[k].to;
        if(y!=ac){
            dfs1(y,x);
            tr[x].siz+=tr[y].siz;
            if(!tr[x].son||tr[y].siz>tr[tr[x].son].siz)tr[x].son=y;
        }
        k=eg[k].nxt;
    }
}

void dfs2(ll x,ll pos){
    tr[x].dfn=++tot;
    tr[x].top=pos;
    if(!tr[x].son)return;
    dfs2(tr[x].son,pos);
    ll k=head[x];
    while(k){
        ll y=eg[k].to;
        if(y!=tr[x].fa&&y!=tr[x].son)dfs2(y,y);
        k=eg[k].nxt;
    } 
}

void mchain(ll x,ll y,ll p){
    while(tr[x].top!=tr[y].top){
        if(tr[tr[x].top].dep<tr[tr[y].top].dep)modify(1,tr[tr[y].top].dfn,tr[y].dfn,p),y=tr[tr[y].top].fa;
        else modify(1,tr[tr[x].top].dfn,tr[x].dfn,p),x=tr[tr[x].top].fa;
    }
    if(tr[x].dep>tr[y].dep)swap(x,y);
    modify(1,tr[x].dfn,tr[y].dfn,p);
}

void solve(){
    scanf("%lld%lld",&n,&m);
    cnt=0;tot=0;
    L(i,1,n)head[i]=0;
    
    L(i,2,n){
        scanf("%lld",&x);
        add(x,i);
    }
    dfs1(1,0);
    dfs2(1,1);
    bd_tree(1,1,n);//L(i,1,n)printf("%lld ",tr[i].dfn);printf("\n");
    while(m--){
        scanf("%lld%lld%lld",&nx,&ny,&nz);
        L(i,1,nx){
            scanf("%lld",&x);
            mchain(1,x,0);
        }
        L(i,1,ny){
            scanf("%lld",&x);
            mchain(1,x,1);
        }
        L(i,1,nz){
            scanf("%lld",&x);
            modify(1,tr[x].dfn,tr[x].dfn+tr[x].siz-1,2);
        }//L(i,1,n)printf("%lld ",query(1,i,i));
        printf("%lld\n",query(1,1,n));
        del();
    }
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll t=1;
    scanf("%lld",&t);
    while(t--)solve();
}
2022杭电多校题解（补题记） 文章被收录于专栏

补完题必写！！

全部评论

相关推荐

11-27 18:28
中南大学 Java
点赞 评论 收藏
分享
11-25 08:35
北京化工大学 后端
在美团两年多的体验
先说说福利吧，工资和年终奖都挺不错的。公司还有免费的健身房和淋浴间，我报了健身团课，瑜伽、舞蹈课都有，员工价超划算，10节课才199元。食堂各种地方的美食都有，而且可以刷公司的饭补，晚上加班还有打车补贴。公司保险和公积金方面也很到位，按工资足额上，给每个人买了商业保险。说到晋升和涨薪，机制也算公平，每年有两次绩效考核，表现好的话能拿到奖金，甚至有机会晋升。不过，跟大厂一样，节奏快、压力大，基本上每天早上十点多到公司，晚上九点多才能走，平均在公司待11小时，工作占据了生活的大部分时间。不过好在有双休。
美团公司福利 1420人发布
点赞 评论 收藏
分享
11-15 22:36
华中师范大学 Java
点赞 评论 收藏
分享
11-11 14:21
西京学院 C++
家人们帮忙看看简历有什么问题，谢谢大家
无敌混子大王：首先一点，不管学校层次怎么样，教育经历放在第一页靠上位置，第一页看不到教育经历，hr基本直接扔掉了
点赞 评论 收藏
分享
11-26 11:35
已编辑
华南农业大学 后端
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
238415次浏览 2042人参与
# ai智能作图 #
31201次浏览 377人参与
# 阿里云管培生offer #
63658次浏览 1764人参与
# 25届秋招总结 #
416049次浏览 4183人参与
# 虾皮求职进展汇总 #
95356次浏览 778人参与
# 地方国企笔面经互助 #
7125次浏览 17人参与
# 北方华创开奖 #
67426次浏览 554人参与
# 实习，投递多份简历没人回复怎么办 #
2442928次浏览 34758人参与
# 我在牛爱网找对象 #
74986次浏览 556人参与
# 机械求职避坑tips #
23947次浏览 251人参与
# 发工资后，你做的第一件事是什么 #
9696次浏览 44人参与
# 我的实习求职记录 #
6137268次浏览 84038人参与
# 25届机械人为了秋招做了哪些准备？ #
26557次浏览 365人参与
# 投格力的你，拿到offer了吗？ #
47629次浏览 337人参与
# 机械人怎么评价今年的华为 #
158153次浏览 1353人参与
# 实习想申请秋招offer，能不能argue薪资 #
36491次浏览 310人参与
# 实习与准备秋招该如何平衡 #
724999次浏览 8566人参与
# 华为工作体验 #
112027次浏览 868人参与
# 如果再来一次，你还会选择这个工作吗？ #
117205次浏览 1151人参与
# 在职场上，你最讨厌什么样的同事 #
6260次浏览 92人参与
# 国央企笔面经互助 #
88707次浏览 897人参与
# 中兴求职进展汇总 #
469858次浏览 2447人参与
牛客网
牛客企业服务