結果

問題 No.619 CardShuffle
ユーザー chocoruskchocorusk
提出日時 2019-01-21 16:59:52
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,095 bytes
コンパイル時間 1,285 ms
コンパイル使用メモリ 103,520 KB
実行使用メモリ 8,744 KB
最終ジャッジ日時 2023-10-13 17:17:05
合計ジャッジ時間 7,227 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
7,500 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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);
			l=i+1;
		}
	}
	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=0;
				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