hdu--4407--一不留神就TLE了

相比于上次我做过的一个容斥题和他很相似就是多了一个modify操作

不过也不难只要通过加加减减操作就能完成了

这个操作我想过很多种方法最后觉得用Map迭代访问是最好的选择

如果遍历x->y这个区间因为y<=400000可能会太大

如果我记录操作1之前执行了多少次的操作2 然后来访问这些操作2 但是可能同一个位置上的数据被多次修改这样统计也会出错

这边使用map还有一个原因就是操作总共也就1000次那么我最差的情况也就是修改了999次询问了1次那map里面最多也就是插入了999个元素很快的

------

然后我的tle也是发生在了map身上还是我自己的思维不好这个加加减减操作被我搞复杂了后来去看了别人的瞬间 fml

 1 void modify( LL x , LL y , LL p )
 2 {
 3     LL a , b c , d;
 4     map<LL,LL>::iterator it;
 5     for( it=mp.begin();it!=mp.end();it++ )
 6     {
 7         c = it->first;
 8         d = it-second;
 9         a = gcd( c , p );
10         b = gcd( d , p );
11         if( it->first == it->second || it->first<=x-1 || it->first >y )
12         {
13             continue;
14         }
15         else if( a==1 )
16         {
17             if( b==1 )
18                 ans = ans - c + d;
19             else
20                 ans = ans - c;
21         }
22         else
23         {
24             if( b==1 )
25                 ans = ans + d;
26         }
27     }
28 }

 1 void modify( LL x , LL y , LL p )
 2 {
 3     map<LL,LL>::iterator it;
 4     for( it=mp.begin();it!=mp.end();it++ )
 5     {
 6         if( it->first == it->second || it->first<=x-1 || it->first >y )
 7         {
 8             continue;
 9         }
10         if( gcd(it->first,p)==1 )
11             ans-=it->first;
12         if( gcd(it->second,p)==1 )
13             ans+=it->second;
14     }
15 }

第一个罗里吧嗦的版本就是我写的真TM 又臭又长啊害我TLE了

  1 #include <iostream>
  2 #include <map>
  3 #include <vector>
  4 using namespace std;
  5 
  6 typedef long long LL;
  7 LL ans;
  8 vector<int> ve;
  9 map<LL,LL>mp;
 10 void getPrime( int n )
 11 {
 12     for( int i = 2 ; i<=n/i ; i++ )
 13     {
 14         if( n%i==0 )
 15         {
 16             ve.push_back( i );
 17             while( n%i==0 )
 18                 n /= i;
 19         }
 20     }
 21     if( n>1 )
 22         ve.push_back( n );
 23 }
 24 
 25 LL gcd( LL x , LL y )
 26 {
 27     return x % y == 0 ? y : gcd( y , x%y );
 28 }
 29 
 30 LL solve( LL x )
 31 {
 32     LL ans = 0 , var , num;
 33     int veSize = ve.size() , cnt;
 34     for( int i = 1 ; i<( 1<<veSize ) ; i++ )
 35     {
 36         var = 1;
 37         cnt = 0;
 38         for( int j = 0 ; j<veSize ; j++ )
 39         {
 40             if( i&(1<<j) )
 41             {
 42                 var = (LL) (var * ve[j]);
 43                 ++ cnt;
 44             }
 45         }
 46         num = x / var;
 47         if( cnt&1 )
 48             ans += num * ( var + num * var ) / 2;
 49         else
 50             ans -= num * ( var + num * var ) / 2;
 51     }
 52     return ans;
 53 }
 54 
 55 void modify( LL x , LL y , LL p )
 56 {
 57     map<LL,LL>::iterator it;
 58     for( it=mp.begin();it!=mp.end();it++ )
 59     {
 60         if( it->first == it->second || it->first<=x-1 || it->first >y )
 61         {
 62             continue;
 63         }
 64         if( gcd(it->first,p)==1 )
 65             ans-=it->first;
 66         if( gcd(it->second,p)==1 )
 67             ans+=it->second;
 68     }
 69 }
 70 
 71 int main()
 72 {
 73     cin.sync_with_stdio(false);
 74     int t , n , m , op;
 75     LL x , y , p , c , ans1 , ans2 , sum1 , sum2;
 76     cin >> t;
 77     while( t-- )
 78     {
 79         cin >> n >> m;
 80         mp.clear();
 81         while( m-- )
 82         {
 83             cin >> op;
 84             if( op==1 )
 85             {
 86                 cin >> x >> y >> p;
 87                 ve.clear( );
 88                 getPrime( p );
 89                 sum1 = (x-1) * x / 2;
 90                 ans1 = solve( x-1 );
 91                 sum2 = y * (y+1) / 2;
 92                 ans2 = solve( y );
 93                 ans = sum2 - ans2 - ( sum1 - ans1 );
 94                 modify( x , y , p );
 95                 cout << ans << endl;
 96             }
 97             else
 98             {
 99                 cin >> x >> c;
100                 mp[x] = c;
101             }
102         }
103     }
104     return 0;
105 }

View Code

这种题目还有一个很烦的地方就是要用到long long或者__int64来处理

today:

　　对于性格外向的女生毫无招架之力

just follow your heart