#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
gp_hash_table<int,int> cnt,cnt2;
const int mod=1e9+7,mod2=1e9+7,m=1e6+1,N=1e6+1;
vector<int> par(N),pwr,pwr2,p,q,hsh(N),hsh2(N);
vector<multiset<int> > imam(N),treba(N);
int n,qq;
ll ans4;
int ans3;
int mul(int a,int b)
{
return (ll)a*b%mod;
}
int mul2(int a,int b)
{
return (ll)a*b%mod2;
}
int add2(int a,int b)
{
a+=b;
if(a>=mod2)
a-=mod2;
return a;
}
int sub2(int a,int b)
{
a-=b;
if(a<0)
a+=mod2;
return a;
}
int add(int a,int b)
{
a+=b;
if(a>=mod)
a-=mod;
return a;
}
int sub(int a,int b)
{
a-=b;
if(a<0)
a+=mod;
return a;
}
int find(int tr)
{
if(par[tr]==tr)
return tr;
return par[tr]=find(par[tr]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(a==b)
return;
cnt2[hsh2[a]]-=imam[a].size();
cnt[hsh[a]]-=imam[a].size();
if(hsh[a]!=0||hsh2[a]!=0)
ans4-=(ll)2*imam[a].size()*min(cnt[sub(0,hsh[a])],cnt2[sub2(0,hsh2[a])]),ans3--;
if(hsh[b]!=0||hsh2[b]!=0)
ans4-=(ll)2*imam[b].size()*min(cnt[sub(0,hsh[b])],cnt2[sub2(0,hsh2[b])]),ans3--;
cnt[hsh[b]]-=imam[b].size();
cnt2[hsh2[b]]-=imam[b].size();
if(imam[a].size()<imam[b].size())
swap(a,b);
for(auto d:imam[b])
hsh[a]=add(hsh[a],pwr[d]),hsh2[a]=add2(hsh2[a],pwr2[d]),imam[a].insert(d);
for(auto d:treba[b])
hsh[a]=sub(hsh[a],pwr[d]),hsh2[a]=sub2(hsh2[a],pwr2[d]),treba[a].insert(d);
imam[b].clear();
treba[b].clear();
par[b]=a;
if(hsh[a]!=0||hsh2[a]!=0)
cnt[hsh[a]]+=imam[a].size(),cnt2[hsh2[a]]+=imam[a].size(),ans4+=(ll)2*imam[a].size()*min(cnt[sub(0,hsh[a])],cnt2[sub2(0,hsh2[a])]),ans3++;
}
void swapuj(int a,int b)
{
int pa=p[a],pb=p[b];
swap(p[a],p[b]);
a=find(a);
b=find(b);
if(a==b)
return;
cnt2[hsh2[a]]-=imam[a].size();
cnt[hsh[a]]-=imam[a].size();
if(hsh[a]!=0||hsh2[a]!=0)
ans4-=(ll)2*imam[a].size()*min(cnt[sub(0,hsh[a])],cnt2[sub2(0,hsh2[a])]),ans3--;
if(hsh[b]!=0||hsh2[b]!=0)
ans4-=(ll)2*imam[b].size()*min(cnt[sub(0,hsh[b])],cnt2[sub2(0,hsh2[b])]),ans3--;
cnt[hsh[b]]-=imam[b].size();
cnt2[hsh2[b]]-=imam[b].size();
hsh[a]=sub(hsh[a],pwr[pa]);
hsh[a]=add(hsh[a],pwr[pb]);
hsh[b]=sub(hsh[b],pwr[pb]);
hsh[b]=add(hsh[b],pwr[pa]);
hsh2[a]=sub2(hsh2[a],pwr2[pa]);
hsh2[a]=add2(hsh2[a],pwr2[pb]);
hsh2[b]=sub2(hsh2[b],pwr2[pb]);
hsh2[b]=add2(hsh2[b],pwr2[pa]);
imam[a].erase(imam[a].find(pa));
imam[a].insert(pb);
imam[b].erase(imam[b].find(pb));
imam[b].insert(pa);
cnt[hsh[a]]+=imam[a].size();
if(hsh[a]!=0||hsh2[a]!=0)
ans4+=(ll)2*imam[a].size()*min(cnt[sub(0,hsh[a])],cnt2[sub2(0,hsh2[a])]),ans3++;
cnt[hsh[b]]+=imam[b].size();
if(hsh[b]!=0||hsh2[b]!=0)
ans4+=(ll)2*imam[b].size()*min(cnt[sub(0,hsh[b])],cnt2[sub2(0,hsh2[b])]),ans3++;
}
int main()
{
//freopen("in.txt","r",stdin);
pwr.pb(1);
pwr2.pb(1);
for(int i=0;i<N;i++)
par[i]=i,pwr.pb(mul(pwr.back(),m)),pwr2.pb(mul2(pwr2.back(),m));
scanf("%i %i",&n,&qq);
p.resize(n);
for(int i=0;i<n;i++)
scanf("%i",&p[i]);
q=p;
sort(all(q));
for(int i=0;i<n;i++)
imam[i].insert(p[i]),hsh[i]=add(hsh[i],pwr[p[i]]),treba[i].insert(q[i]),hsh[i]=sub(hsh[i],pwr[q[i]]),cnt[hsh[i]]++,hsh2[i]=add2(hsh2[i],pwr2[p[i]]),hsh2[i]=sub2(hsh2[i],pwr2[q[i]]),cnt2[hsh2[i]]++;
for(int i=0;i<n;i++)
if(hsh[i]!=0||hsh2[i]!=0)
ans4+=min(cnt[sub(0,hsh[i])],cnt2[sub2(0,hsh2[i])]),ans3++;
while(qq--)
{
int t,a,b;
scanf("%i",&t);
if(t==1)
scanf("%i %i",&a,&b),swapuj(a-1,b-1);
if(t==2)
scanf("%i %i",&a,&b),merge(a-1,b-1);
if(t==3)
printf(ans3==0?"DA\n":"NE\n");
if(t==4)
printf("%lld\n",ans4/2);
}
return 0;
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&qq);
~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&p[i]);
~~~~~^~~~~~~~~~~~
zamjene.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&t);
~~~~~^~~~~~~~~
zamjene.cpp:160:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&a,&b),swapuj(a-1,b-1);
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:162:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&a,&b),merge(a-1,b-1);
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
114120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
114056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
114016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
114064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
114088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
115152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
236 ms |
125012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1766 ms |
183748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1991 ms |
286112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1739 ms |
223892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
