Problem: holes (2017 finals)

Kit is a young, obedient Fox who excels in his studies, diligently practices
his hunting skills, and is always friendly. His parents couldn't be prouder!
That is, except for one problem... he refuses to eat his vegetables!

In an effort to improve Kit's diet, his parents have set up a little game for
him to play. They've dug a series of 2**N** \+ 2 small holes in a row on the
ground, and numbered them from 0 to 2**N** \+ 1, from first to last. They've
left the first and last holes empty, and filled the remaining 2**N** holes
with one healthy vegetable each! There are **N** different types of
vegetables, numbered from 1 to **N**, and a vegetable of type **Vi** has
initially been placed into each hole _i_, such that exactly 2 vegetables of
each type were used in total.

Kit must start inside hole 0, and jump forwards from hole to hole until he
reaches hole 2**N** \+ 1. When he's inside any given hole _i_, he's agile
enough to jump to either hole _i_ \+ 1 or directly to hole _i_ \+ 2, but he
can't jump any further than that at once. Whenever he lands in a hole
containing a vegetable, the rules of the game mandate that he must eat it!

Kit has agreed to play this game (not that he has much choice in the matter),
but there's only so much he can take. The vegetables are tolerable as long as
there's variety. He doesn't care how many he has to eat in total, but he
absolutely refuses to eat multiple vegetables of any single type over the
course of the game. In other words, for each vegetable type, he must only
enter _at most_ one of the two holes containing that vegetable on his way from
hole 0 to hole 2**N** \+ 1.

Kit will play the game once per day for a period of **M** days. For some fun
variety, at the start of each day _i_, his parents will swap the contents of
two different holes **Ai** and **Bi**. Then, Kit will play the game using the
current configuration of vegetables. Once he's done, his parents will replace
any vegetables which he had eaten with new vegetables of the same types, thus
resetting the game to the state it was in before Kit played it.

Each day, there might be no acceptable way for Kit to complete the game, or
there might be many different ways for him to do so. Two ways are considered
different if at least one hole is visited in one but not the other. In order
to make the game more exciting for himself, Kit would like to count up the
number of different ways he could potentially complete it each day. However,
that's a lot of big numbers to keep track of, so he's only interested in the
sum of these **M** values when taken modulo 1,000,000,007. Please help him
compute this overall sum!

### Input

Input begins with an integer **T**, the number of different rows of holes. For
each row of holes, there is first a line containing the space-separated
integers **N** and **M**. There is next a line containing 2**N** space-
separated integers, the _i_th of which is **Vi**. Then **M** lines follow, the
_i_th of which contains the space-separated integers **Ai** and **Bi**

### Output

For the _i_th row of holes, print a line containing "Case #**i**: " followed
by a single integer, the sum of the **M** days' answers modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 30  
1 ≤ **N, M** ≤ 500,000  
1 ≤ **Ai**, **Bi** ≤ 2**N**  
1 ≤ **Vi** ≤ **N**  
Both the sum of **N** values and the sum of **M** values across all **T**
cases do not exceed 2,000,000.

### Explanation of Sample

In the first case, both holes 1 and 2 will contain vegetables of type 1 even
after their contents are swapped. There are then 2 different ways for Kit to
validly reach hole 3 from hole 0, visiting either of these sequences of holes:

      0 -> 1 -> 3
      0 -> 2 -> 3

He can't quite jump far enough to reach hole 3 directly from hole 0, nor can
he visit both holes 1 and 2, as that would require eating multiple vegetables
of a single type.

In the second case, there are 2 different ways for Kit to validly complete the
game on the first day, and only 1 way on the second day. This results in a
final answer of (2 + 1) modulo 1,000,000,007 = 3.



Sample input:
5
1 1
1 1
1 2
2 2
1 2 1 2
3 4
3 4
4 4
2 4 3 2 1 4 1 3
4 5
3 5
3 4
3 1
5 5
4 3 5 3 4 1 1 5 2 2
2 6
3 9
1 3
3 10
7 10
8 12
2 8 7 4 1 5 2 7 6 3 4 6 5 1 8 3
1 4
1 2
2 15
14 6
10 11
1 10
15 13
10 16
3 12
15 5
1 8
12 7


Sample output:
Case #1: 2
Case #2: 3
Case #3: 5
Case #4: 0
Case #5: 17



Code: // Hacker Cup 2017
// Final Round
// Fox Holes
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define MOD 1000000007
#define LIM 1100000

int L[LIM],A[LIM],B[LIM];
int sz,treeM[LIM],treeC[LIM],lazy[LIM];
set<int> SL,SR;

void Prop(int i)
{
	int v=lazy[i],j=i<<1,k=j+1;
	lazy[i]=0;
	treeM[i]+=v;
		if (i<sz)
			lazy[j]+=v,lazy[k]+=v;
}

void Update(int i,int r1,int r2,int a,int b,int v)
{
		if (a>b)
			return;
	Prop(i);
		if ((a<=r1) && (r2<=b))
		{
			lazy[i]+=v;
			return;
		}
	int m=(r1+r2)>>1,j=i<<1,k=j+1;
		if (a<=m)
			Update(j,r1,m,a,b,v);
		if (b>m)
			Update(k,m+1,r2,a,b,v);
	Prop(j),Prop(k);
	treeM[i]=min(treeM[j],treeM[k]);
	treeC[i]=0;
		if (treeM[i]==treeM[j])
			treeC[i]+=treeC[j];
		if (treeM[i]==treeM[k])
			treeC[i]+=treeC[k];
}

int Query(int i,int r1,int r2,int a,int b)
{
		if (a>b)
			return(0);
	Prop(i);
		if ((a<=r1) && (r2<=b))
			return(treeM[i] ? 0 : treeC[i]);
	int m=(r1+r2)>>1,j=i<<1,k=j+1,v=0;
		if (a<=m)
			v+=Query(j,r1,m,a,b);
		if (b>m)
			v+=Query(k,m+1,r2,a,b);
	return(v);
}

void Go(int i,int d)
{
	int a=A[i],b=B[i],p;
		if (a>b)
			swap(a,b);
	p=b-a;
		if (p%2)
		{
			// odd difference, key point must be outside [a, b-1]
			a/=2,b/=2;
			Update(1,0,sz-1,a,b-1,d);
			return;
		}
	// even difference, key point must be inside [a, b-1]
		if (d<0)
		{
			SL.erase(a);
			SR.erase(b-2);
		}
		else
		{
			SL.insert(a);
			SR.insert(b-2);
		}
}

int main()
{
	// vars
	int T,t;
	int N,M;
	int i,j,a,b;
	int ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input, init pairs
			Read(N),Read(M);
			Fill(A,-1);
				Fox(i,N<<1)
				{
					Read(j),j--;
					L[i]=j;
						if (A[j]<0)
							A[j]=i;
						else
							B[j]=i;
				}
			// init data structures
				for(sz=1;sz<=N;sz<<=1);
			Fill(lazy,0);
			Fill(treeM,0);
				Fox(i,sz)
					treeC[sz+i]=1;
				FoxR1(i,sz-1)
					treeC[i]=treeC[i*2]+treeC[i*2+1];
			SL.clear(),SR.clear();
			// insert pairs
				Fox(i,N)
					Go(i,1);
			// process updates
			ans=0;
				while (M--)
				{
					// input
					Read(i),Read(j),i--,j--;
					a=L[i],b=L[j];
						if (a==b)
							goto Skip;
					// remove pairs
					Go(a,-1),Go(b,-1);
					// update pairs
					swap(L[i],L[j]);
						if (A[a]==i)
							A[a]=j;
						else
							B[a]=j;
						if (A[b]==j)
							A[b]=i;
						else
							B[b]=i;
					// re-insert pairs
					Go(a,1),Go(b,1);
Skip:;
					// compute current answer
						if (SL.empty())
							a=0,b=N*2;
						else
						{
							a=*SL.rbegin();
							b=*SR.begin();
						}
					a/=2;
					b/=2;
					ans=(ans+Query(1,0,sz-1,a,b))%MOD;
				}
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}