結果

問題 No.619 CardShuffle
コンテスト
ユーザー chocorusk
提出日時 2019-01-21 16:59:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,095 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 105,284 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 13:12:31
合計ジャッジ時間 7,516 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 4 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

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