Hi, all!↵
↵
This is not [user:Tommyr7,2017-10-06], but the **impostor** behind the round (guess who I am? :P). The statements are written by me. The characters in the round feature, again, the _Monogatari_ anime series, and to be more specific, _Nisemonogatari: Fake Tale_. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
On a side note, special kudos to [the best impostors of the round](http://codeforces.com/blog/entry/54971?#comment-389321) (except me, lol)!↵
↵
Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!↵
↵
Here are hints for all problems and detailed tutorials for most of them. Stay tuned, more are coming!↵
↵
<hr>↵
↵
### Hints↵
↵
<spoiler summary="Problem A">↵
First approach: Optimize the straightforward solution.↵
↵
<spoiler summary="... or even...">↵
Second approach: Believe in magic.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B">↵
Multiply instead of divide. What happens to the last digit when multiplying?↵
</spoiler>↵
↵
<spoiler summary="Problem C">↵
Consider islands of **two** colours and the bridges between them.↵
</spoiler>↵
↵
<spoiler summary="Problem D">↵
Iterate over all possible combination, order and direction of extra edges.↵
</spoiler>↵
↵
<spoiler summary="Problem E">↵
First approach: 2D segment tree (or quadtree) with a `set` or `vector` on each node, representing the set of barriers that cover this node.↵
↵
<spoiler summary="... or may as well...">↵
Second approach: Assign a random value to each barrier. Then utilise 2D Fenwick trees.↵
</spoiler>↵
↵
</spoiler>↵
↵
<hr>↵
↵
### Tutorials↵
↵
### [problem:869A]↵
**Author** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869A]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define Maxn 4000007↵
bool vis[Maxn];↵
int a[4007],b[4007],n;↵
int main()↵
{↵
scanf("%d",&n);↵
memset(vis,false,sizeof(vis));↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&a[i]);↵
vis[a[i]]=true;↵
}↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&b[i]);↵
vis[b[i]]=true;↵
}↵
int ans=0;↵
for (int i=1;i<=n;i++)↵
for (int j=1;j<=n;j++)↵
if (vis[a[i]^b[j]]) ++ans;↵
if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (cyand1317)">↵
~~~~~↵
#include <stdio.h>↵
↵
int main()↵
{↵
puts("Karen");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869B]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869B]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long L,R;↵
int ans;↵
int main()↵
{↵
scanf("%lld%lld",&L,&R);↵
if (R-L>=10) printf("%d\n",0);↵
else↵
{↵
ans=1;↵
for (long long i=L+1;i<=R;i++)↵
ans=(1LL*ans*(i%10))%10;↵
printf("%d\n",ans);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869C]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:Tommyr7,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869C]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 5007↵
#define modp 998244353↵
int p[Maxn][Maxn];↵
int pre[Maxn];↵
int a,b,c;↵
int solve(int x,int y)↵
{↵
int res=0;↵
for (int k=0;k<=x&&k<=y;k++)↵
{↵
int del=pre[k];↵
del=(1LL*del*p[x][k])%modp;↵
del=(1LL*del*p[y][k])%modp;↵
res=(res+del)%modp;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&a,&b,&c);↵
memset(p,0,sizeof(p));↵
p[0][0]=1;↵
for (int i=1;i<=5000;i++)↵
{↵
p[i][0]=1;↵
for (int j=1;j<=i;j++)↵
p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;↵
}↵
memset(pre,0,sizeof(pre));↵
pre[0]=1;↵
for (int i=1;i<=5000;i++)↵
pre[i]=(1LL*pre[i-1]*i)%modp;↵
int ans=1;↵
ans=(1LL*ans*solve(a,b))%modp;↵
ans=(1LL*ans*solve(b,c))%modp;↵
ans=(1LL*ans*solve(a,c))%modp;↵
printf("%d\n",ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869D]↵
**Author** [user:quailty,2017-10-06] / **Preparation** [user:quailty,2017-10-06] / **Tutorial** [user:quailty,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869D]↵
</spoiler>↵
↵
<spoiler summary="Model solution (quailty)">↵
~~~~~↵
#include<cstdio>↵
#include<cstdlib>↵
#include<cstring>↵
#include<cmath>↵
#include<iostream>↵
#include<algorithm>↵
#include<map>↵
↵
using namespace std;↵
↵
const int MAXN=255;↵
↵
const int Mod=1000000007;↵
inline void add_mod(int &x,int y)↵
{↵
x=(x+y<Mod ? x+y : x+y-Mod);↵
}↵
↵
int u[MAXN],v[MAXN];↵
↵
map<int,int> mp;↵
inline int get_id(int x)↵
{↵
if(!mp[x])mp[x]=(int)mp.size();↵
return mp[x];↵
}↵
↵
vector<int> e[MAXN];↵
void add_edge(int u,int v)↵
{↵
e[u].push_back(v);↵
e[v].push_back(u);↵
}↵
↵
inline int cal_size(int u,int n,int d)↵
{↵
int t=u,c=0,res;↵
while(t)c++,t>>=1;↵
res=(1<<(d-c+1))-1,t=c;↵
while(t<d)t++,u=u<<1|1;↵
return res-max(min(u-n,1<<(d-c)),0);↵
}↵
↵
int num[MAXN];↵
void pre_dp(int u,int f)↵
{↵
for(auto &v:e[u])↵
{↵
if(v==f)continue;↵
num[u]-=num[v];↵
pre_dp(v,u);↵
}↵
}↵
↵
int vis[MAXN];↵
void dfs(int u,int &tot)↵
{↵
add_mod(tot,num[u]);↵
vis[u]=1;↵
for(auto &v:e[u])↵
if(!vis[v])dfs(v,tot);↵
vis[u]=0;↵
}↵
↵
int main()↵
{↵
int n,m,d=0;↵
scanf("%d%d",&n,&m);↵
while((1<<d)<=n)d++;↵
get_id(1);↵
for(int i=0;i<m;i++)↵
{↵
scanf("%d%d",&u[i],&v[i]);↵
int t=u[i];↵
while(t)get_id(t),t>>=1;↵
t=v[i];↵
while(t)get_id(t),t>>=1;↵
}↵
for(auto &t:mp)↵
{↵
int u=t.first,id=t.second;↵
if(u>1)add_edge(get_id(u),get_id(u>>1));↵
num[id]=cal_size(u,n,d);↵
}↵
pre_dp(1,0);↵
for(int i=0;i<m;i++)↵
add_edge(get_id(u[i]),get_id(v[i]));↵
int res=0;↵
for(int i=1;i<=(int)mp.size();i++)↵
{↵
int tot=0;↵
dfs(i,tot);↵
add_mod(res,1LL*tot*num[i]%Mod);↵
}↵
printf("%d\n",res);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869E]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06], [user:visitWorld,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869E]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1 (visitWorld)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)↵
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define pb push_back↵
#define bin(x) (1<<(x))↵
//#define LX_JUDGE↵
↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }↵
template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }↵
↵
template<typename T> inline void read(T &x) {↵
char c;↵
while ((c = getchar()) < '0' or c > '9');↵
for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');↵
}↵
↵
const int inf = 0x3f3f3f3f;↵
const int MAX_N = 2500;↵
↵
struct Data {↵
int u, d, id;↵
Data() {}↵
Data(int u, int d, int id) : u(u), d(d), id(id) {}↵
};↵
↵
class SegmentTree {↵
map<pii, int> G;↵
int n, pcnt;↵
vector<Data> H[MAX_N * 4 + 255];↵
#define ls (o << 1)↵
#define rs (o << 1 | 1)↵
↵
int _l, _r, _u, _d, _id;↵
↵
void ins(int o, int l, int r) {↵
if (_l <= l and r <= _r) {↵
//printf("%d %d %d %d\n", l, r, _u, _d);↵
H[o].pb(Data(_u, _d, _id));↵
return ;↵
}↵
int m = (l + r) / 2;↵
if (_l <= m) ins(ls, l, m);↵
if (m < _r) ins(rs, m + 1, r);↵
}↵
void del(int o, int l, int r) {↵
if (_l <= l and r <= _r) {↵
for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {↵
if (it->id == _id) {↵
H[o].erase(it);↵
break ;↵
}↵
}↵
return ;↵
}↵
int m = (l + r) / 2;↵
if (_l <= m) del(ls, l, m);↵
if (m < _r) del(rs, m + 1, r);↵
}↵
inline int _ask(const vector<Data> &q, int h) {↵
int best = inf, ans = -1;↵
for (auto to : q) {↵
if (to.u <= h and h <= to.d and to.d - to.u < best) {↵
best = to.d - to.u;↵
ans = to.id;↵
}↵
}↵
return ans;↵
}↵
int ask(int o, int l, int r) {↵
if (l == r) return _ask(H[o], _u);↵
int m = (l + r) / 2;↵
int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);↵
return ans < 0 ? _ask(H[o], _u) : ans;↵
}↵
#undef ls↵
#undef rs↵
public :↵
void init(int n) {↵
this->n = n;↵
pcnt = 1;↵
}↵
void ins(int l, int u, int r, int d) {↵
G[mp(l, u)] = _id = pcnt++;↵
_l = l, _r = r, _u = u, _d = d;↵
ins(1, 1, n);↵
}↵
void del(int l, int u, int r, int d) {↵
_id = G[mp(l, u)];↵
G.erase(mp(l, u));↵
_l = l, _r = r;↵
del(1, 1, n);↵
}↵
int ask(int x, int y) {↵
_l = x, _u = y;↵
return ask(1, 1, n);↵
}↵
} my;↵
↵
int main() {↵
int n, m, Q;↵
read(n), read(m), read(Q);↵
my.init(2500); // FIX ME↵
int opt, r1, c1, r2, c2;↵
while (Q--) {↵
read(opt), read(r1), read(c1), read(r2), read(c2);↵
if (opt == 3) {↵
//int a = my.ask(r1, c1), b = my.ask(r2, c2);↵
//printf("%d %d\n", a, b);↵
puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");↵
} else if (opt == 1) {↵
my.ins(r1, c1, r2, c2);↵
} else {↵
my.del(r1, c1, r2, c2);↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 2507↵
using namespace std;↵
int n,m,q;↵
map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;↵
pair<unsigned long long,unsigned long long> s[Maxn][Maxn];↵
void add(int x,int y,pair<unsigned long long,unsigned long long> del)↵
{↵
for (int kx=x;kx<=2503;kx+=kx&(-kx))↵
for (int ky=y;ky<=2503;ky+=ky&(-ky))↵
{↵
s[kx][ky].first+=del.first;↵
s[kx][ky].second+=del.second;↵
}↵
}↵
pair<unsigned long long,unsigned long long> query(int x,int y)↵
{↵
pair<unsigned long long,unsigned long long> res=make_pair(0,0);↵
for (int kx=x;kx;kx-=kx&(-kx))↵
for (int ky=y;ky;ky-=ky&(-ky))↵
{↵
res.first+=s[kx][ky].first;↵
res.second+=s[kx][ky].second;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&n,&m,&q);↵
memset(s,0,sizeof(s));↵
srand(20001206);↵
mp.clear();↵
for (int i=1;i<=q;i++)↵
{↵
int t,r1,c1,r2,c2;↵
scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);↵
pair<unsigned long long,unsigned long long> del,udel;↵
if (t==1)↵
{↵
del.first=rand();↵
del.second=rand();↵
udel=make_pair(-del.first,-del.second);↵
mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;↵
add(r1,c1,del);↵
add(r1,c2+1,udel);↵
add(r2+1,c1,udel);↵
add(r2+1,c2+1,del);↵
} else if (t==2)↵
{↵
del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];↵
mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);↵
udel=make_pair(-del.first,-del.second);↵
add(r1,c1,udel);↵
add(r1,c2+1,del);↵
add(r2+1,c1,del);↵
add(r2+1,c2+1,udel);↵
}↵
else↵
{↵
del=query(r1,c1);↵
udel=query(r2,c2);↵
if (del==udel) printf("Yes\n"); else printf("No\n");↵
}↵
}↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
<hr>↵
↵
**Tommyr7: I do hope you all enjoyed yourselves during the contest. See you next time!**
↵
This is not [user:Tommyr7,2017-10-06], but the **impostor** behind the round (guess who I am? :P). The statements are written by me. The characters in the round feature, again, the _Monogatari_ anime series, and to be more specific, _Nisemonogatari: Fake Tale_. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!↵
↵
On a side note, special kudos to [the best impostors of the round](http://codeforces.com/blog/entry/54971?#comment-389321) (except me, lol)!↵
↵
Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!↵
↵
Here are hints for all problems and detailed tutorials
↵
<hr>↵
↵
### Hints↵
↵
<spoiler summary="Problem A">↵
First approach: Optimize the straightforward solution.↵
↵
<spoiler summary="... or even...">↵
Second approach: Believe in magic.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B">↵
Multiply instead of divide. What happens to the last digit when multiplying?↵
</spoiler>↵
↵
<spoiler summary="Problem C">↵
Consider islands of **two** colours and the bridges between them.↵
</spoiler>↵
↵
<spoiler summary="Problem D">↵
Iterate over all possible combination, order and direction of extra edges.↵
</spoiler>↵
↵
<spoiler summary="Problem E">↵
First approach: 2D segment tree (or quadtree) with a `set` or `vector` on each node, representing the set of barriers that cover this node.↵
↵
<spoiler summary="... or may as well...">↵
Second approach: Assign a random value to each barrier. Then utilise 2D Fenwick trees.↵
</spoiler>↵
↵
</spoiler>↵
↵
<hr>↵
↵
### Tutorials↵
↵
### [problem:869A]↵
**Author** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869A]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define Maxn 4000007↵
bool vis[Maxn];↵
int a[4007],b[4007],n;↵
int main()↵
{↵
scanf("%d",&n);↵
memset(vis,false,sizeof(vis));↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&a[i]);↵
vis[a[i]]=true;↵
}↵
for (int i=1;i<=n;i++)↵
{↵
scanf("%d",&b[i]);↵
vis[b[i]]=true;↵
}↵
int ans=0;↵
for (int i=1;i<=n;i++)↵
for (int j=1;j<=n;j++)↵
if (vis[a[i]^b[j]]) ++ans;↵
if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (cyand1317)">↵
~~~~~↵
#include <stdio.h>↵
↵
int main()↵
{↵
puts("Karen");↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869B]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869B]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
long long L,R;↵
int ans;↵
int main()↵
{↵
scanf("%lld%lld",&L,&R);↵
if (R-L>=10) printf("%d\n",0);↵
else↵
{↵
ans=1;↵
for (long long i=L+1;i<=R;i++)↵
ans=(1LL*ans*(i%10))%10;↵
printf("%d\n",ans);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869C]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06] / **Tutorial** [user:Tommyr7,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869C]↵
</spoiler>↵
↵
<spoiler summary="Model solution (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 5007↵
#define modp 998244353↵
int p[Maxn][Maxn];↵
int pre[Maxn];↵
int a,b,c;↵
int solve(int x,int y)↵
{↵
int res=0;↵
for (int k=0;k<=x&&k<=y;k++)↵
{↵
int del=pre[k];↵
del=(1LL*del*p[x][k])%modp;↵
del=(1LL*del*p[y][k])%modp;↵
res=(res+del)%modp;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&a,&b,&c);↵
memset(p,0,sizeof(p));↵
p[0][0]=1;↵
for (int i=1;i<=5000;i++)↵
{↵
p[i][0]=1;↵
for (int j=1;j<=i;j++)↵
p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;↵
}↵
memset(pre,0,sizeof(pre));↵
pre[0]=1;↵
for (int i=1;i<=5000;i++)↵
pre[i]=(1LL*pre[i-1]*i)%modp;↵
int ans=1;↵
ans=(1LL*ans*solve(a,b))%modp;↵
ans=(1LL*ans*solve(b,c))%modp;↵
ans=(1LL*ans*solve(a,c))%modp;↵
printf("%d\n",ans);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869D]↵
**Author** [user:quailty,2017-10-06] / **Preparation** [user:quailty,2017-10-06] / **Tutorial** [user:quailty,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869D]↵
</spoiler>↵
↵
<spoiler summary="Model solution (quailty)">↵
~~~~~↵
#include<cstdio>↵
#include<cstdlib>↵
#include<cstring>↵
#include<cmath>↵
#include<iostream>↵
#include<algorithm>↵
#include<map>↵
↵
using namespace std;↵
↵
const int MAXN=255;↵
↵
const int Mod=1000000007;↵
inline void add_mod(int &x,int y)↵
{↵
x=(x+y<Mod ? x+y : x+y-Mod);↵
}↵
↵
int u[MAXN],v[MAXN];↵
↵
map<int,int> mp;↵
inline int get_id(int x)↵
{↵
if(!mp[x])mp[x]=(int)mp.size();↵
return mp[x];↵
}↵
↵
vector<int> e[MAXN];↵
void add_edge(int u,int v)↵
{↵
e[u].push_back(v);↵
e[v].push_back(u);↵
}↵
↵
inline int cal_size(int u,int n,int d)↵
{↵
int t=u,c=0,res;↵
while(t)c++,t>>=1;↵
res=(1<<(d-c+1))-1,t=c;↵
while(t<d)t++,u=u<<1|1;↵
return res-max(min(u-n,1<<(d-c)),0);↵
}↵
↵
int num[MAXN];↵
void pre_dp(int u,int f)↵
{↵
for(auto &v:e[u])↵
{↵
if(v==f)continue;↵
num[u]-=num[v];↵
pre_dp(v,u);↵
}↵
}↵
↵
int vis[MAXN];↵
void dfs(int u,int &tot)↵
{↵
add_mod(tot,num[u]);↵
vis[u]=1;↵
for(auto &v:e[u])↵
if(!vis[v])dfs(v,tot);↵
vis[u]=0;↵
}↵
↵
int main()↵
{↵
int n,m,d=0;↵
scanf("%d%d",&n,&m);↵
while((1<<d)<=n)d++;↵
get_id(1);↵
for(int i=0;i<m;i++)↵
{↵
scanf("%d%d",&u[i],&v[i]);↵
int t=u[i];↵
while(t)get_id(t),t>>=1;↵
t=v[i];↵
while(t)get_id(t),t>>=1;↵
}↵
for(auto &t:mp)↵
{↵
int u=t.first,id=t.second;↵
if(u>1)add_edge(get_id(u),get_id(u>>1));↵
num[id]=cal_size(u,n,d);↵
}↵
pre_dp(1,0);↵
for(int i=0;i<m;i++)↵
add_edge(get_id(u[i]),get_id(v[i]));↵
int res=0;↵
for(int i=1;i<=(int)mp.size();i++)↵
{↵
int tot=0;↵
dfs(i,tot);↵
add_mod(res,1LL*tot*num[i]%Mod);↵
}↵
printf("%d\n",res);↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
### [problem:869E]↵
**Author** [user:Tommyr7,2017-10-06] / **Preparation** [user:Tommyr7,2017-10-06], [user:cyand1317,2017-10-06], [user:visitWorld,2017-10-06] / **Tutorial** [user:cyand1317,2017-10-06]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:869E]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1 (visitWorld)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)↵
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define pb push_back↵
#define bin(x) (1<<(x))↵
//#define LX_JUDGE↵
↵
using namespace std;↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
↵
template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }↵
template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }↵
↵
template<typename T> inline void read(T &x) {↵
char c;↵
while ((c = getchar()) < '0' or c > '9');↵
for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');↵
}↵
↵
const int inf = 0x3f3f3f3f;↵
const int MAX_N = 2500;↵
↵
struct Data {↵
int u, d, id;↵
Data() {}↵
Data(int u, int d, int id) : u(u), d(d), id(id) {}↵
};↵
↵
class SegmentTree {↵
map<pii, int> G;↵
int n, pcnt;↵
vector<Data> H[MAX_N * 4 + 255];↵
#define ls (o << 1)↵
#define rs (o << 1 | 1)↵
↵
int _l, _r, _u, _d, _id;↵
↵
void ins(int o, int l, int r) {↵
if (_l <= l and r <= _r) {↵
//printf("%d %d %d %d\n", l, r, _u, _d);↵
H[o].pb(Data(_u, _d, _id));↵
return ;↵
}↵
int m = (l + r) / 2;↵
if (_l <= m) ins(ls, l, m);↵
if (m < _r) ins(rs, m + 1, r);↵
}↵
void del(int o, int l, int r) {↵
if (_l <= l and r <= _r) {↵
for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {↵
if (it->id == _id) {↵
H[o].erase(it);↵
break ;↵
}↵
}↵
return ;↵
}↵
int m = (l + r) / 2;↵
if (_l <= m) del(ls, l, m);↵
if (m < _r) del(rs, m + 1, r);↵
}↵
inline int _ask(const vector<Data> &q, int h) {↵
int best = inf, ans = -1;↵
for (auto to : q) {↵
if (to.u <= h and h <= to.d and to.d - to.u < best) {↵
best = to.d - to.u;↵
ans = to.id;↵
}↵
}↵
return ans;↵
}↵
int ask(int o, int l, int r) {↵
if (l == r) return _ask(H[o], _u);↵
int m = (l + r) / 2;↵
int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);↵
return ans < 0 ? _ask(H[o], _u) : ans;↵
}↵
#undef ls↵
#undef rs↵
public :↵
void init(int n) {↵
this->n = n;↵
pcnt = 1;↵
}↵
void ins(int l, int u, int r, int d) {↵
G[mp(l, u)] = _id = pcnt++;↵
_l = l, _r = r, _u = u, _d = d;↵
ins(1, 1, n);↵
}↵
void del(int l, int u, int r, int d) {↵
_id = G[mp(l, u)];↵
G.erase(mp(l, u));↵
_l = l, _r = r;↵
del(1, 1, n);↵
}↵
int ask(int x, int y) {↵
_l = x, _u = y;↵
return ask(1, 1, n);↵
}↵
} my;↵
↵
int main() {↵
int n, m, Q;↵
read(n), read(m), read(Q);↵
my.init(2500); // FIX ME↵
int opt, r1, c1, r2, c2;↵
while (Q--) {↵
read(opt), read(r1), read(c1), read(r2), read(c2);↵
if (opt == 3) {↵
//int a = my.ask(r1, c1), b = my.ask(r2, c2);↵
//printf("%d %d\n", a, b);↵
puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");↵
} else if (opt == 1) {↵
my.ins(r1, c1, r2, c2);↵
} else {↵
my.del(r1, c1, r2, c2);↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Tommyr7)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define Maxn 2507↵
using namespace std;↵
int n,m,q;↵
map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;↵
pair<unsigned long long,unsigned long long> s[Maxn][Maxn];↵
void add(int x,int y,pair<unsigned long long,unsigned long long> del)↵
{↵
for (int kx=x;kx<=2503;kx+=kx&(-kx))↵
for (int ky=y;ky<=2503;ky+=ky&(-ky))↵
{↵
s[kx][ky].first+=del.first;↵
s[kx][ky].second+=del.second;↵
}↵
}↵
pair<unsigned long long,unsigned long long> query(int x,int y)↵
{↵
pair<unsigned long long,unsigned long long> res=make_pair(0,0);↵
for (int kx=x;kx;kx-=kx&(-kx))↵
for (int ky=y;ky;ky-=ky&(-ky))↵
{↵
res.first+=s[kx][ky].first;↵
res.second+=s[kx][ky].second;↵
}↵
return res;↵
}↵
int main()↵
{↵
scanf("%d%d%d",&n,&m,&q);↵
memset(s,0,sizeof(s));↵
srand(20001206);↵
mp.clear();↵
for (int i=1;i<=q;i++)↵
{↵
int t,r1,c1,r2,c2;↵
scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);↵
pair<unsigned long long,unsigned long long> del,udel;↵
if (t==1)↵
{↵
del.first=rand();↵
del.second=rand();↵
udel=make_pair(-del.first,-del.second);↵
mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;↵
add(r1,c1,del);↵
add(r1,c2+1,udel);↵
add(r2+1,c1,udel);↵
add(r2+1,c2+1,del);↵
} else if (t==2)↵
{↵
del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];↵
mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);↵
udel=make_pair(-del.first,-del.second);↵
add(r1,c1,udel);↵
add(r1,c2+1,del);↵
add(r2+1,c1,del);↵
add(r2+1,c2+1,udel);↵
}↵
else↵
{↵
del=query(r1,c1);↵
udel=query(r2,c2);↵
if (del==udel) printf("Yes\n"); else printf("No\n");↵
}↵
}↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
<hr>↵
↵
**Tommyr7: I do hope you all enjoyed yourselves during the contest. See you next time!**
