結果

問題 No.619 CardShuffle
ユーザー chocoruskchocorusk
提出日時 2019-01-21 17:18:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 314 ms / 3,000 ms
コード長 3,157 bytes
コンパイル時間 1,059 ms
コンパイル使用メモリ 106,804 KB
実行使用メモリ 9,556 KB
最終ジャッジ日時 2024-09-15 13:13:28
合計ジャッジ時間 7,324 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 238 ms
8,164 KB
testcase_17 AC 239 ms
9,556 KB
testcase_18 AC 238 ms
8,260 KB
testcase_19 AC 240 ms
9,344 KB
testcase_20 AC 172 ms
6,940 KB
testcase_21 AC 174 ms
8,392 KB
testcase_22 AC 163 ms
9,216 KB
testcase_23 AC 180 ms
8,264 KB
testcase_24 AC 164 ms
9,432 KB
testcase_25 AC 111 ms
6,944 KB
testcase_26 AC 294 ms
8,192 KB
testcase_27 AC 310 ms
9,408 KB
testcase_28 AC 289 ms
8,192 KB
testcase_29 AC 314 ms
9,344 KB
testcase_30 AC 223 ms
6,940 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 171 ms
6,940 KB
testcase_33 AC 239 ms
8,264 KB
testcase_34 AC 249 ms
8,208 KB
testcase_35 AC 162 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAX_N=1<<17;
const ll MOD=1e9+7;
int n;
char c[100001];
set<int> ind;
int m; ll prod[2*MAX_N];
void init(int m_){
	m=1;
	while(m<m_) m<<=1;
	for(int i=m; i<=2*m-1; i++){
		prod[i]=1;
	}
	for(int i=m+1; i<m+m_; i+=2){
		prod[i]=(c[i-m]-'0');
	}
	for(int i=m-1; i>=1; i--){
		prod[i]=prod[2*i]*prod[2*i+1]%MOD;
	}
}

void update(int k, ll a){
	k+=m;
	prod[k]=a;
	while(k>1){
		k>>=1;
		prod[k]=prod[2*k]*prod[2*k+1]%MOD;
	}
}

ll query(int a, int b){
	a+=m, b+=m;
	ll ans=1;
	for(;a<b; a>>=1, b>>=1){
		if(b&1) ans=ans*prod[--b]%MOD;
		if(a&1) ans=ans*prod[a++]%MOD;
	}
	return ans;
}

ll bit[100001];
ll sump[100001];
ll sum(int i){
	ll s=0;
	while(i>0){
		s+=bit[i]; s%=MOD;
		i-=(i&(-i));
	}
	return s;
}
 
void add(int i, ll x){
	while(i<=n){
		bit[i]+=x; bit[i]%=MOD;
		i+=(i&(-i));
	}
}

int main()
{
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>c[i];
		if(c[i]=='+') ind.insert(i);
	}
	init(n+1);
	int l=1;
	for(int i=2; i<=n; i+=2){
		if(c[i]=='+'){
			sump[l]=query(l, i);
			add(l, sump[l]);
			l=i+1;
		}
	}
	sump[l]=query(l, n+1);
	add(l, sump[l]);
	int q; cin>>q;
	for(int i=0; i<q; i++){
		char t; int x, y;
		cin>>t>>x>>y;
		if(t=='!'){
			if(x&1){
				ll xc=prod[x+m], yc=prod[y+m];
				update(x, yc); update(y, xc);
				auto itr=ind.lower_bound(x);
				int l, r;
				if(itr==ind.end()) r=n+1;
				else r=*itr;
				if(ind.empty() || itr==ind.begin()) l=1;
				else{
					itr--;
					l=(*itr)+1;
				}
				ll s1=query(l, r);
				add(l, (s1-sump[l]+MOD)%MOD);
				sump[l]=s1;
				itr=ind.lower_bound(y);
				if(itr==ind.end()) r=n+1;
				else r=*itr;
				if(ind.empty() || itr==ind.begin()) l=1;
				else{
					itr--;
					l=(*itr)+1;
				}
				s1=query(l, r);
				add(l, (s1-sump[l]+MOD)%MOD);
				sump[l]=s1;
			}else{
				if(c[x]==c[y]) continue;
				if(c[x]=='+') swap(x, y);
				c[x]='+';
				auto itr=ind.lower_bound(x); int l, r;
				if(itr==ind.end()) r=n+1;
				else r=*itr;
				if(ind.empty() || itr==ind.begin()) l=1;
				else{
					itr--;
					l=(*itr)+1;
				}
				ll s1=query(l, x);
				add(l, (s1-sump[l]+MOD)%MOD);
				sump[l]=s1;
				s1=query(x, r);
				add(x+1, (s1-sump[x+1]+MOD)%MOD);
				sump[x+1]=s1;
				ind.insert(x);
				
				c[y]='*';
				itr=ind.lower_bound(y);
				itr++;
				if(itr==ind.end()) r=n+1;
				else r=*itr;
				itr--;
				if(itr==ind.begin()) l=1;
				else{
					itr--; l=(*itr)+1;
				}
				add(y+1, (MOD-sump[y+1])%MOD);
				sump[y+1]=0;
				s1=query(l, r);
				add(l, (s1-sump[l]+MOD)%MOD);
				sump[l]=s1;
				ind.erase(y);
			}
		}else{
			auto itr1=ind.lower_bound(x), itr2=ind.lower_bound(y);
			if(itr1==itr2){
				cout<<query(x, y+1)<<endl;
				continue;
			}
			itr2--;
			int r=*itr2, l=*itr1;
			ll ans=(query(r, y+1)+query(x, l)+sum(r)-sum(l)+MOD)%MOD;;
			cout<<ans<<endl;
		}
	}
	return 0;
}
0