#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef LOCAL
const int mxN=50;
#else
const int mxN=1e6+5; //make sure this is right
#endif
const int mod=1e9+7;
const int b=131;
ll fpow(ll b,ll e){
ll res=1;
while(e){
if(e&1)
res=(res*b)%mod;
b=(b*b)%mod;
e>>=1;
}
return res;
}
ll divmod(ll a,ll b){
return (a*fpow(b,mod-2))%mod;
}
map<int,ll> cnt;
ll uf[mxN],hp[mxN],hq[mxN],ans,sub;
int tot,bad[mxN];
int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);}
void add2(int id,ll v,int x){
if(id==0) return;
id=(id+mod)%mod;
ll s=abs(uf[x]);
ans-=cnt[id]*(cnt[id]-1)/2;
cnt[id]+=v*s;
sub+=(s*(s-1)/2)*v;
if(!cnt[id]) cnt.erase(id);
else ans+=cnt[id]*(cnt[id]-1)/2;
}
void add(int x,int idx,int v){
add2(hp[x]-hq[x],-1,x);
add2(hq[x]-hp[x],-1,x);
ll exp=fpow(b,idx)*v;
hp[x]=(hp[x]+exp+mod)%mod;
add2(hp[x]-hq[x],1,x);
add2(hq[x]-hp[x],1,x);
}
void unite(int x,int y){
x=find(x); y=find(y);
if(x==y) return;
if(uf[x]>uf[y]) swap(x,y);
tot-=bad[x]; tot-=bad[y];
add2(hp[x]-hq[x],-1,x);
add2(hq[x]-hp[x],-1,x);
add2(hp[y]-hq[y],-1,y);
add2(hq[y]-hp[y],-1,y);
uf[x]+=uf[y]; uf[y]=x;
hp[x]=(hp[x]+hp[y])%mod;
hq[x]=(hq[x]+hq[y])%mod;
bad[x]=(hp[x]!=hq[x]);
tot+=bad[x];
add2(hp[x]-hq[x],1,x);
add2(hq[x]-hp[x],1,x);
}
/*
hp[i] + hp[j] = hq[i] + hq[j]
hp[i] - hq[i] = hq[j] - hp[j]
*/
int a[mxN],s[mxN];
ll calc(int x){
return abs(uf[x])*(abs(uf[x])-1)/2;
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,q; cin>>n>>q;
memset(uf,-1,sizeof(uf));
for(int i=1;i<=n;i++){
cin>>a[i];
hp[i]=fpow(b,a[i]);
s[i]=a[i];
}
sort(s+1,s+1+n);
for(int i=1;i<=n;i++){
hq[i]=fpow(b,s[i]);
bad[i]=(hp[i]!=hq[i]);
tot+=bad[i];
add2(hq[i]-hp[i],1,i);
add2(hp[i]-hq[i],1,i);
}
while(q--){
int op; cin>>op;
if(op==1){
int i,j; cin>>i>>j;
if(find(i)==find(j)) continue;
int x=find(i); int y=find(j);
tot-=bad[x]; tot-=bad[y];
add(x,a[i],-1);
add(y,a[j],-1);
swap(a[i],a[j]);
add(x,a[i],1);
add(y,a[j],1);
bad[x]=(hp[x]!=hq[x]);
bad[y]=(hp[y]!=hq[y]);
tot+=bad[x]; tot+=bad[y];
} else if(op==2){
int i,j; cin>>i>>j;
unite(i,j);
} else if(op==3){
cout<<(tot?"NE\n":"DA\n");
} else{
cout<<(ans-sub)/2<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
8592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
12356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2522 ms |
29092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4682 ms |
57596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2185 ms |
42628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
