#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(n+1);
}
void update(int x,int y){
x++;
for(;x<=n;x+=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
x++;
int ans=0;
for(;x>0;x-=(x&-x)){
ans+=bt[x];
}
return ans;
}
};
const int mod=1e9+7;
void add(int& x,int y){
x+=y;
x-=mod*(x>=mod);
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int po(int x,int y){
int z=1;
while(y){
if(y&1){
z=mul(z,x);
}
x=mul(x,x);
y>>=1;
}
return z;
}
int main(){
AquA;
vector<int> p2(1e5+7);
p2[0]=1;
for(int i=1;i<100007;i++){
p2[i]=mul(p2[i-1],2);
}
int n;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
int q;
cin >> q;
const int A=8;
vector<vector<vector<int> > > pre(A,vector<vector<int> >(A,vector<int>(n)));
vector<vector<vector<pair<int,int> > > > vq(A,vector<vector<pair<int,int> > >(A));
for(int i=0;i<q;i++){
int l,r,x;
cin >> l >> r >> x;
l--;
r--;
for(int j=0;j<A;j++){
if((x>>j)&1){
for(int k=0;k<A;k++){
if((x>>k)&1){
vq[j][k].push_back({l,r});
pre[j][k][l]++;
if(r+1<n){
pre[j][k][r+1]--;
}
}
}
}
}
}
int ans=0;
for(int j=0;j<A;j++){
for(int k=0;k<A;k++){
for(int i=1;i<n;i++){
pre[j][k][i]+=pre[j][k][i-1];
}
}
}
for(int j=0;j<A;j++){
for(int l=0;l<A;l++){
BIT bt;
bt.init(n);
vector<vector<int> > ct(n,vector<int>(n));
sort(vq[j][l].begin(),vq[j][l].end(),[&](pair<int,int> a,pair<int,int> b){return a.sc<b.sc;});
int ll=0;
for(auto h:vq[j][l]){
bt.update(h.fs,1);
}
for(int i=0;i<n;i++){
for(int k=0;k<=i;k++){
ct[i][k]=bt.query(k);
}
while(ll<(int)vq[j][l].size() && vq[j][l][ll].sc==i){
bt.update(vq[j][l][ll].fs,-1);
ll++;
}
}
for(int i=0;i<n;i++){
for(int k=0;k<n;k++){
int z=1;
if(i!=k){
z=1;
}
int a=ct[i][k],b=pre[j][l][i]-a,c=pre[j][l][k]-a;
int now=p2[q-a-b-c];
int x=(v[i]>>j)&1,y=(v[k]>>l)&1;
for(int h=0;h<2;h++){
if(h==1 && a==0){
continue;
}
if(a==0){
now=mul(now,p2[a]);
}
else{
now=mul(now,p2[a-1]);
}
if(h==1){
x^=1;
y^=1;
}
if(x==0 && b==0){
now=0;
}
if(y==0 && c==0){
now=0;
}
if(b==0){
now=mul(now,p2[b]);
}
else{
now=mul(now,p2[b-1]);
}
if(c==0){
now=mul(now,p2[c]);
}
else{
now=mul(now,p2[c-1]);
}
add(ans,mul(z,mul(mul(now,p2[j+l]),mul(k+1,n-i))));
if(now!=0){
//cout << j << " " << l << " " << i << " " << k << " " << mul(z,mul(mul(now,p2[j+l]),mul(k+1,n-i))) << "\n";
}
now=p2[q-a-b-c];
}
/*
if(b==0 && c==0){
if(((((v[i]>>j)&1) xor ((v[k]>>l)&1)))==1){
continue;
}
if(a==0 && ((v[i]>>j)&1)==0){
continue;
}
else{
if(a==0){
add(ans,mul(z,mul(mul(p2[max(q,0)],p2[l+j]),mul(k+1,n-i))));
}
else{
add(ans,mul(z,mul(mul(p2[max(q-1,0)],p2[l+j]),mul(k+1,n-i))));
}
continue;
}
}
if(pre[j][l][i]==0 && ((v[i]>>j)&1)==0){
continue;
}
if(pre[j][l][k]==0 && ((v[k]>>l)&1)==0){
continue;
}
int u=((b==0)&(c==0));
u+=(a==0);
add(ans,mul(p2[u],mul(z,mul(mul(p2[max(q-2,0)],p2[l+j]),mul(k+1,n-i)))));
*/
}
}
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
7500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1229 ms |
5336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
